题解：P16850 [GKS 2021 #D] Cutting Intervals

· · 题解

思路

多测不清空，虚空调试两小时，我已急哭。

发现题目相当于选 C 个被最多区间覆盖的点，容易想到差分，一看数据范围发现需要离散化。

由于区间的端点切不了，然后离散化完中间的点可能会直接被压掉，所以离散化的时候加入一个 L_i+1 来确保中间点离散化后仍然存在。

再记录一下离散化后的每个点相当于原来几个点就行了。

代码

#include<bits/stdc++.h>
#define int long long
#define For(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int N=3e5+10;
int t,n,c,l[N],r[N],lsh[N],d[N],sum[N],a[N];
struct sut{
    int cnt,w;
}s[N];
bool cmp(sut x,sut y){
    return x.cnt>y.cnt;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    For(ca,1,t){
        cin>>n>>c;
        int cnt=0;
        memset(d,0,sizeof(d));
        For(i,1,n){
            cin>>l[i]>>r[i];
            lsh[++cnt]=l[i],lsh[++cnt]=r[i],lsh[++cnt]=l[i]+1;
        }
        sort(lsh+1,lsh+cnt+1);
        int len=unique(lsh+1,lsh+cnt+1)-lsh-1;
        For(i,1,n){
            l[i]=lower_bound(lsh+1,lsh+len+1,l[i])-lsh;
            r[i]=lower_bound(lsh+1,lsh+len+1,r[i])-lsh;
            d[l[i]+1]++,d[r[i]]--;
        }
        For(i,1,len-1) sum[i]=sum[i-1]+d[i],s[i].cnt=sum[i];
        For(i,1,len-1) a[i]=lsh[i+1]-lsh[i],s[i].w=a[i];
        sort(s+1,s+len,cmp);
        int ans=0;
        int i=1;
        while(c&&i<len){
            if(s[i].w<=c) c-=s[i].w,ans+=s[i].w*s[i].cnt;
            else ans+=c*s[i].cnt,c=0;
            i++;
        }
        cout<<"Case #"<<ca<<": "<<ans+n<<'\n';
    }
    return 0;
}