题解 P9975

· · 题解

题意：

初始有一些区域为 1，每一天每个 1 都会向左右蔓延一格，问某个情景下，最少有多少个初始 1。

思路：

所有连通块中的 1 必须蔓延时间相同。于是一个显然的贪心就是，蔓延时间越大，初始 1 就越少。

但 0 无法蔓延，因此最大的时间 t 取决于最小的那个连通块。t=\lceil\dfrac{minblk}{2}\rceil。

最后，设初始时间 t=1，t 时间内一个初始 1 能够带走 t\times 2-1 大小的范围，因此只需计算每个连通块大小除以 t\times 2-1（上取整）之和即可。

细节：左右靠边的连通块需要单独计算 t，由于抵着边界，无需除以二下取整。

程序如下：

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<cstring>
using namespace std;
const int N=3e5+5;
int n,m,stb,edb,a[N],cnt,ans;
char str[N];
int main(){
    scanf("%d%s",&n,str+1);
    int st=1,ed=n;
    while(str[st]=='1')st++,stb++;
    while(str[ed]=='1')ed--,edb++;
    for(int i=st;i<=ed;i++){
        if(str[i]=='1'){
            cnt++;
            while(str[i]=='1')i++,a[cnt]++;
        }
    }
    sort(a+1,a+cnt+1);
    int tm=2e9;
    if(a[1]!=0)tm=min(tm,(a[1]+1)/2);
    if(stb!=0)tm=min(stb,tm);//要先确认左右不是0再取min
    if(edb!=0)tm=min(edb,tm);
    for(int i=1;i<=cnt;i++)ans+=ceil((double)(a[i])/(tm*2-1.));
    ans+=ceil((double)stb/(tm*2-1));
    if(st<=ed)ans+=ceil((double)edb/(tm*2-1));
    printf("%d\n",ans);
    return 0;
}

THE END