CF1804D

题解

一道贪心题。注意到长度为

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)

。

代码

CPP

#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;
}

文章操作

题解

代码

相关推荐

评论

CF1804D