首页 > 代码库 > Codeforces Round #422 C
Codeforces Round #422 C
Hacker, pack your bags!
题意:给n个区间,每个区间的长度为ri-li+1,权值为ci,选取2个不相交的区间,长度加起来为x,且权值和最小
思路:遍历 l ,vi[l]存起点为l的区间的权值最小值,每次加入li==l的区间更新vi的值,更新后再更新ri==l-1的答案,这样可以保证,每次选择一个区间后,从vi里选择的另一个区间一定是不相交的
AC代码:
#include<bits/stdc++.h> #include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #define ll long long #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a) memset(a,0,sizeof(a)) #define mp(x,y) make_pair(x,y) #define pb push_back const long long INF = 1e18+1LL; const int inf = 1e9+1e8; using namespace std; const int N=1e5+100; vector<pair<ll,ll> > vexl[2*N],vexr[2*N]; ll n,x,vi[2*N],mk[2*N]; int main(){ for(int i=0; i<=2e5; ++i) vi[i]=2LL*inf; //for(int i=1; i<=10; ++i) cout<<vi[i]<<" "; ll ans=2LL*inf; scanf("%lld%lld",&n,&x); int li,ri,ma=0; ll ci; for(int i=1; i<=n; ++i){ scanf("%d%d%lld",&li,&ri,&ci); ma=max(ma,ri); vexl[li].pb(mp(ri,ci)); vexr[ri].pb(mp(li,ci)); } for(int l=ma; l>0; --l){ for(auto j :vexl[l]){ int len=j.first-l+1; mk[len]=1,vi[len]=min(vi[len],j.second); //cout<<j.second<<endl; } int r=l-1; for(auto j :vexr[r]){ int len=x-(r-j.first+1); if(len>0 && mk[len]){ ans=min(ans,j.second+vi[len]); //cout<<len<<" "<<r<<" "<<j.second<<" "<<vi[len]<<endl; } } } if(ans==2LL*inf) printf("-1"); else printf("%lld",ans); return 0; }
Codeforces Round #422 C
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。