题意

给出一些闭区间（始末+代价），选取两段不重合区间使长度之和恰为x且代价最低

思路

相同持续时间的放在一个vector中，内部再对起始时间排序，从后向前扫获取对应起始时间的最优代价，存在minn中，对时间 i 从前向后扫，在对应的k-i中二分找第一个不重合的区间，其对应的minn加上 i 的cost即为出发时间为 i 时的最优解

代码

#include
     
      using namespace std;int n, k;struct EVE{    int st,ed,val;    EVE(){    }    EVE(int a,int b, int c){        st = a, ed = b, val = c;    }};int f,t,c;vector
      
        v[200200];vector
       
         minn[200200];int tmp[200200];bool cmp(EVE a, EVE b){    return a.st
        
         = k) continue;        v[t-f+1].push_back({f,t,c});    }    for(int i = 1;i<=k;i++) sort(v[i].begin(),v[i].end(),cmp);    for(int i = 1;i<=k;i++){        for(int j = v[i].size()-1;j>=0;j--){            if(j==v[i].size()-1) tmp[j]=v[i][j].val;            else tmp[j]=min(v[i][j].val,tmp[j+1]);        }        for(int j = 0;j
         
          >1;            while(le
          
           >1; if(v[k-i][mid].st<=ed) le = mid+1; else ri = mid; } ans = min(ans, cost+minn[k-i][le]); } } if(ans == 1e12) printf("-1"); else printf("%I64d",ans); return 0;}