题目大意：给你n个旅券，上面有开始时间l,结束时间r，和花费cost，要求选择两张时间不相交的旅券时间长度相加为x,且要求花费最少。
解题思路：看了大佬的才会写!其实和之前Codeforces 776C的写法有点像，遍历l,设以l为起始时间时长为time,看是否存在时长为x-time且与当前时段不相交的时间段，取最小值。
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 using namespace std; 6 const int N=2e5+5; 7 typedef pair<int,int>pii; 8 9 vector<pii>v[N];//存放拿来拼凑的区段 10 vector<pii>rc[N];//用来存放接下来要遍历的区段 11 int mp[N]; 12 13 int main(){ 14 ios::sync_with_stdio(false); 15 int n,x; 16 cin>>n>>x; 17 for(int i=1;i<=n;i++){ 18 int l,r,cost; 19 cin>>l>>r>>cost; 20 //以l为索引存放区段 21 rc[l].push_back(pii(r,cost)); 22 } 23 int ans=2e9+1; 24 //遍历l的值 25 for(int l=1;l<=2e5;l++){ 26 for(int i=0;i<rc[l].size();i++){ 27 int r=rc[l][i].first; 28 int cost=rc[l][i].second; 29 int time=r-l+1; 30 if(time>x) 31 continue; 32 //看是否存在与这段时间相加和为x,且不想交的时段 33 if(mp[x-time]){ 34 ans=min(ans,mp[x-time]+cost); 35 } 36 //遍历过的放到左边区域 37 v[r].push_back(pii(time,cost)); 38 } 39 //找v[l],也就是左边区域的v[r]，因为下一次l2=l+1,肯定大于r,所以区间不会相交,可以直接拿来用 40 for(int i=0;i<v[l].size();i++){ 41 int time=v[l][i].first; 42 int cost=v[l][i].second; 43 if(!mp[time]||mp[time]>cost) 44 mp[time]=cost; 45 } 46 } 47 if(ans==2e9+1) 48 cout<<-1<<endl; 49 else 50 cout<<ans<<endl; 51 }