CF822C Hacker, pack your bags!(思维)-白红宇

CF822C Hacker, pack your bags!(思维)

阅读量：4684 次

发布时间：2019-06-09

本文共 1509 字，大约阅读时间需要 5 分钟。

Hacker, pack your bags

【题目链接】

&题意：

有n条线段(n<=2e5) 每条线段有左端点li，右端点ri，价值cost（1 <= li <= ri <= 2e5, cost <= 1e9)

对于一个给定的x(x <= 2e5)，寻找两个不相交的线段，使它们的长度和恰好为x，并且价值和最小

&题解：

只有2个线段,并且他们的和是定值x.但是还有另外一个条件,他们的区间不相交,这个我们可以通过排序左端点l来实现,当我们排序完l,那么任意一个r在这个l之前的都可以与这条线段相组合,那么可以设一个mi[i]:表示线段长度为i时的最小花费,mi[i]可以通过r是否在这个l之前来更新.

&代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              using namespace std;#define ll long long#define fo(i,a,b) for(int i=(a);i<=(b);i++)#define fd(i,a,b) for(int i=(a);i>=(b);i--)#define cle(a,v) memset(a,(v),sizeof(a))const int maxn = 2e5 + 7, inf = 2e9 + 9;int n, x, cnt, mi[maxn];struct Gro { int a, b, co, dur, sta;} a[maxn << 1];bool cmp (Gro a, Gro b) { return a.a < b.a || a.a == b.a && a.sta > b.sta;}int main() { freopen("E:1.in", "r", stdin); cle(mi, -1); scanf("%d%d", &n, &x); fo(i, 0, n - 1) { int x, y, z; scanf("%d%d%d", &x, &y, &z); a[cnt++] = Gro{x, y, z, y - x + 1, 1}; a[cnt++] = Gro{y, x, z, y - x + 1, -1}; } sort(a, a + cnt, cmp); int ans = inf; fo(i, 0, cnt - 1) { // printf("%d %d %d \n", a[i].a, a[i].b, a[i].dur); if(a[i].sta == 1) { if(a[i].dur < x && mi[x - a[i].dur] != -1) { ans = min(ans, mi[x - a[i].dur] + a[i].co); } } else { if(a[i].dur < x && (mi[a[i].dur] == -1 || mi[a[i].dur] > a[i].co)) { mi[a[i].dur] = a[i].co; } } } printf("%d\n", ans == inf ? -1 : ans); return 0;}

转载于:https://www.cnblogs.com/s1124yy/p/7140795.html

你可能感兴趣的文章