HDU 6119 小小粉丝度度熊（区间和并+尺取）

 

 

这个题目一上来我们知道合并要合并区间 ，因为给的都是闭区间，所以在合并区间时要注意

之后便可以尺取过程了，但在每一步尺取过程中，我们依然要计算区间长度及区间间隔，所以我们需要预处理一部，避免问题复杂化

在之后的尺取过程中，我们要注意样例二 ： 将所有间隔补充完成后，若还有剩余，可以向后继续补签

 

typedef pair<int,int> Pair; const int N=1e5+5; int n,m,t; int i,j,k; Pair p[N]; int val[N],wigh[N]; //记录区间长度，区间间隔 bool cmp(Pair a,Pair b) { if(a.fr!=b.fr) return a.fr<b.fr; return a.sc<b.sc; } int main() { IOS; while(cin>>n>>m){ for(i=1;i<=n;i++){ cin>>p[i].fr>>p[i].sc; } sort(p+1,p+1+n,cmp); //合并区间 int num=0,L=p[1].fr,R=p[1].sc; for(i=2;i<=n;i++){ if(R+1>=p[i].fr){ R=max(R,p[i].sc); L=min(L,p[i].fr); } else{ p[++num]=Pair{ L,R }; L=p[i].fr , R=p[i].sc; } } p[++num]=Pair{ L,R }; //计算将区间连接起来的价值及花费 for(i=1;i<=num;i++){ val[i]=p[i].sc-p[i].fr+1; //区间长度 if(i!=num) wigh[i]=p[i+1].fr-p[i].sc-1; //区间间隔 } //尺取 int ans=0,s=1,e=2,cost=0,tmp=val[1]; while(s<=num){ while(e<=num && cost+wigh[e-1]<=m){ cost += wigh[e-1]; //将 e 区间连接到尾部 tmp += (wigh[e-1]+val[e]); //e-1 后面的间隔 + e 区间的长度 e++; } ans=max(ans,tmp+m-cost); //样例二提示 if(e>num) break; tmp -= (wigh[s]+val[s]); //将区间断开，并去掉间隔 cost -= wigh[s]; s++; } cout<<ans<<endl; } //PAUSE; return 0; }