P9046 题解

前言

贪心，然而假了两次。

思路

考虑简化一下问题，相当于给定多个区间（对应全 0 区间），这些区间两边在不断扩展，每秒可以给任意区间加隔板，求最少能扩展的长度。

对于某个区间，超过一定时间后就不再产生贡献，于是考虑按照这个时间降序排列，优先向时间长的区间加隔板。发现最左和最右的区间是特殊的，他们只能在一边扩展，但是同样也能对其维护时间。

为什么这个贪心是对的？如果存在一个每秒的增量 d，那么每过一秒，增量会减少所有达到限制时间的区间的限制，无论对于什么区间，每次操作会减去 1 的增量，那么每次选择时间最大的区间操作，可以保证剩下的区间的限制时间尽量小。

还有个小细节，增量为 2 的区间在操作一次后会变成一个更长的增量为 1 的区间，当然可以直接使用优先队列维护，但是发现操作一次后的区间限制时间更长了，所以下一次还是对其操作，因此直接两次一起减（注意剩余长度小的时候的特判）。

算是贪心里套贪心了？

总之打得很不爽，纪念一下。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
struct hbr{
    int s;
    int d;
}q[N];
bool operator <(hbr a,hbr b){
    return a.s*2/a.d>b.s*2/b.d;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        int num=0,fl=0;
        int ans=n,t=0,cnt=0;
        for(int i=1;i<=n;i++){
            char c;
            cin>>c;
            if(c=='0'){
                num++;
            }else{
                if(!fl){
                    fl=1;
                    q[++cnt]={num,1};
                }else{
                    q[++cnt]={num,2};
                }
                num=0;
            }
        }
        q[++cnt]={num,1};
        sort(q+1,q+1+cnt);
        for(int i=1;i<=cnt;i++){
            int s=q[i].s,d=q[i].d;
            s-=d*t;
            if(s<=0)break;
            if(d==1){
                ans-=s;
                t++;
            }else{
                if(s==1||s==2){
                    ans--;
                    t++;
                }else{
                    ans-=s-1;
                    t+=2;
                }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}