hdu-6119 小小粉丝度度熊 尺取

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6119

 

题意：

      给你n个连续的区间，这些数字都被标红（区间可重叠），现在你有m次机会可以将不红的点标红，问你连续的标红的点的个数最大是多少

做法：

      简单尺取，预处理做好就可以了。

---

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=100005;
struct node{
    ll l,r;
    bool operator < (const node &a) const {
        if(l==a.l) return r<a.r;
        return l<a.l;
    }
}e[maxn];
ll n,k;
int init(){
    sort(e+1,e+1+n);
    int now=1;
    for(int i=2;i<=n;i++){
        if(e[i].l<=e[now].r+1){
            if(e[i].r>e[now].r){
                e[now].r=e[i].r;
            }
        }
        else {
            e[++now]=e[i];
        }
    }
    return now;
}
ll Clen(int i){
    return e[i].r-e[i].l+1;
}
int main(){

    while(~scanf("%lld%lld",&n,&k)){
        for(int i=1;i<=n;i++){
            scanf("%lld%lld",&e[i].l,&e[i].r);
        }
        n=init();
        ll ans=0,r=1,num=0,tans=Clen(1);
        for(int l=1;l<=n;l++){
            while(num<=k&&r+1<=n){
                r++;
                num+=e[r].l-e[r-1].r-1;
                tans+=Clen(r);
            }
            if(num>k){
                num-=e[r].l-e[r-1].r-1;
                tans-=Clen(r);
                r--;
            }
            ans=max(ans,tans+k);
            tans-=Clen(l);
            num-=e[l+1].l-e[l].r-1;
        }
        printf("%lld\n",ans);
    }

    return 0;
}