CF1804D

DDF_ · 2025-11-15 09:49:10 · 题解

题解

一道贪心题。注意到长度为 2 的块对答案的限制作用最大，所以根据不同情况去放。从连续两个位置去看，发现有 \{0,1\}，\{1,0\}，\{0,0\}，\{1,1\} 四种情况。其中，只有 \{1,1\} 的块放长度为 2 的会让答案比放长度为 1 的减小 1，所以去看所有的连续的两个位置，来求最大值和最小值。

对于求最小值，要最大化答案减小量，那就尽量让 \{1,1\} 的块全放长度为 2 的。

对于求最大值，要最小化答案减小量，那就尽量让 \{0,1\}，\{1,0\}，\{0,0\} 的块放长度为 2 的，留空间给长度为 1 的放在 \{1,1\} 里。

结，时间复杂度 O(nm)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,ansmn,ansmx;
char a[N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>(a+1);
        int resmn=0,resmx=0,res=0;
        int cnt=0;
        for(int j=1;j<=m;j++) if(a[j]=='1') res++;
        for(int j=1;j<m;j++) if(a[j]=='1'&&a[j+1]=='1'&&cnt<m/4) j++,cnt++,resmn++;
        cnt=0;
        for(int j=1;j<m;j++) if((a[j]!='1'||a[j+1]!='1')&&(cnt<m/4)) j++,cnt++,resmx++;
        ansmn+=res-resmn,ansmx+=res-(m/4-resmx);
    }
    printf("%d %d",ansmn,ansmx);
    return 0;
}