题目大意是给若干线段及其费用，每个线段权值即为其长度。要求找出两个不重合线段，令其权值和等于x且费用最少。
解法：
先分析一下题目，要处理不重合的问题，有重合的线段不能组合，其次这是一个选二问题，当枚举其中一条线段时，另一条合法线段的必要条件“权值”可以直接得出。
对于第一个问题，想到先对线段根据l进行排序，这样每次枚举一个线段的时候，如果在它的l之后有一个合法线段，我们只要标记一下x-LenNow，待枚举到那个合法线段的时候自然就判断出来了。如果在它之前有一个合法线段符合条件，根据刚刚的做法我们自然可以处理。现在问题就是，万一它不合法，它重合呢？解决方法就是延迟标记它。对于线段们，我们已经对l排序，那么一旦枚举到一条线段的l大于等于之前待标记的某线段的r，那它及之后的线段都不会与它重合，而之前的线段（标记线段之后的线段）一定与它重合。所以我们维护一个优先队列，以待标记的r进行排序，每次枚举前，根据枚举到线段的l将部分待标记物执行标记即可。
撤了那么多，看看代码吧。
#include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <queue> #define LL long long int using namespace std; struct node { LL r,len,c; friend bool operator < (node a,node b) { return a.r>b.r; } };//用于延迟标记 struct cd { LL l,r,c; }; LL mi[200005]; const LL inf=3000000000; vector<cd> v; bool cmp(cd a,cd b) { if(a.l==b.l) return a.r<b.r; return a.l<b.l; } int main() { LL n,x; while(cin>>n>>x) { LL a,b,c; LL ans=inf; v.clear(); fill(mi,mi+200000,inf); priority_queue<node> upt; for(LL i=0;i<n;i++) { cin>>a>>b>>c; v.push_back((cd){a,b,c}); } sort(v.begin(),v.end(),cmp); for(int i=0;i<v.size();i++) { while(!upt.empty()) { node check=upt.top(); if(v[i].l<=check.r) break; upt.pop(); if(mi[check.len]>check.c) mi[check.len]=check.c; } cd now=v[i]; LL len=now.r-now.l+1; LL f=x-len; upt.push((node){now.r,len,now.c}); if(f<=0) continue; if(now.c+mi[f]<ans) ans=now.c+mi[f]; } if(ans!=inf) cout<<ans<<endl; else cout<<-1<<endl; } return 0; }