Codeforces Round #422 (Div. 2) C. Hacker, pack your bags!

题目链接：Codeforces Round #422 (Div. 2) C. Hacker, pack your bags!

题意：

有n条线段，现在让你找两条线段，使得这两条不重合并且两条线段的长度和为x。

然后使得这两条线段的价值最小。

题解：

先将所有线段按照左端点排序，然后将对应长度的线段扔进容器里。

然后枚举每个线段，在对应的x-len的容器中去找左端点大于这条右端点并且价值最小的线段就行了。

这里可以用二分查找，然后求一个后缀最小值就行了。

二分查找到的位置idx [idx,end]这个区间的线段全部都可以，所以求一下后缀最小值就可以快速的查询。

还在一种扫描的方法，将每个端点放进对于的容器内，然后从1到N挨着扫过去，对应更新答案，具体看代码。

法一：

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 typedef long long ll;
 5 #define ___ freopen("c:\code\in.txt","r",stdin);
 6 const int N=2e5+7;
 7 
 8 struct Node
 9 {
10     int l,r,v;
11     Node(int a=0,int b=0,int c=0):l(a),r(b),v(c){}
12     bool operator <(const Node &b)const{return l<b.l;}
13 }a[N];
14 
15 vector<Node>V[N];
16 vector<int>suf[N];
17 int n,m,mxlen;
18 
19 int main()
20 {
21     scanf("%d%d",&n,&m);
22     F(i,1,n)
23     {
24         int l,r,v;
25         scanf("%d%d%d",&l,&r,&v);
26         a[i]=Node(l,r,v);
27     }
28     sort(a+1,a+1+n);
29     F(i,1,n)
30     {
31         int len=a[i].r-a[i].l+1;
32         mxlen=max(mxlen,len);
33         V[len].push_back(a[i]);
34     }
35     F(i,0,mxlen)
36     {
37         int mi=INT_MAX,sz=V[i].size();
38         suf[i].resize(sz);
39         if(!sz)continue;
40         for(int j=sz-1;j>=0;j--)
41         {
42             mi=min(mi,V[i][j].v);
43             suf[i][j]=mi;
44         }
45     }
46     int ans=INT_MAX;
47     F(i,1,n)
48     {
49         int len=a[i].r-a[i].l+1;
50         if(V[m-len].size()==0||m-len<=0)continue;
51         int idx=lower_bound(V[m-len].begin(),V[m-len].end(),Node(a[i].r+1))-V[m-len].begin();
52         if(idx<suf[m-len].size())
53             ans=min(ans,a[i].v+suf[m-len][idx]);
54     }
55     printf("%d
",ans==INT_MAX?-1:ans);
56     return 0;
57 }

View Code

法二：

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 typedef long long ll;
 5 typedef pair<int,int>P;
 6 const int N=2e5+7;
 7 
 8 int n,m;
 9 vector<P>L[N],R[N];
10 ll c[N],ans;
11 int main()
12 {
13     F(i,1,N-1)c[i]=INT_MAX;
14     scanf("%d%d",&n,&m);
15     F(i,1,n)
16     {
17         int l,r,v;
18         scanf("%d%d%d",&l,&r,&v);
19         L[l].push_back({r-l+1,v});
20         R[r].push_back({r-l+1,v});
21     }
22     ans=INT_MAX;
23     F(i,1,N-1)
24     {
25         for(auto &it:L[i])
26         {
27             if(it.first>=m)continue;
28             ans=min(ans,c[m-it.first]+it.second);
29         }
30         for(auto &it:R[i])
31             c[it.first]=min(c[it.first],1ll*it.second);
32     }
33     printf("%I64d
",ans==INT_MAX?-1:ans);
34     return 0;
35 }

View Code