首页 > 代码库 > #422(div2)C. Hacker, pack your bags!

#422(div2)C. Hacker, pack your bags!

2024-10-16 00:17:39   210人阅读

题意：给出n个区间和X，每个区间有左右边界和价值,li,ri,x。然后问从这n个区间找出2个不重合的区间，他们的区间长度和为x，并且价值最小

思路：我们可以预处理出每个长度所包含的区间，然后可以保存每个区间L的位置，和R的位置，那么在某个位置（某个L），前面的都是无重合，在判断下X-当前区间的长度

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const long long INF=1e18;
 5 const int N=2e5+10;
 6 
 7  vector<pair <LL ,LL > > l[N],r[N];
 8  vector<pair <LL ,LL > >::iterator it;
 9 LL c[N];
10 
11 int main(){
12     int n,x;
13     int ll,rr,v;
14     scanf("%d%d",&n,&x);
15     for(int i=1;i<=n;i++){
16         scanf("%d%d%d",&ll,&rr,&v);
17         l[ll].push_back(make_pair(rr-ll+1,v));
18         r[rr].push_back(make_pair(rr-ll+1,v));
19     }
20     for(int i=1;i<=200000;i++) c[i]=INF;
21     LL ans=INF;
22     for(int i=1;i<=200000;i++){
23         for(int j=0;j<l[i].size();j++){
24             int y=l[i][j].first;
25             if(y>=x) continue;
26             if(c[x-y]!=INF) ans=min(ans,c[x-y]+l[i][j].second);
27         }
28         for(int j=0;j<r[i].size();j++){
29             int y=r[i][j].first;
30             c[y]=min(c[y],r[i][j].second);
31         }
32     }
33     if(ans==INF) cout<<-1<<endl;
34     else
35     cout<<ans<<endl;
36 }

 

#422(div2)C. Hacker, pack your bags!


联系
我们