NC214436. 肥猪的钢琴床
描述
肥猪很喜欢睡懒觉，与此同时肥猪十分喜欢买各种各样神奇的床。
今天肥猪买了一张很宽很宽的钢琴床，肥猪就在上面滚来滚去。
这张钢琴床十分的有趣，因为它被分为n个部分，每一个部分是凸起来或者凹下去的，可是肥猪十分不喜欢相邻两个位置高低不同，因为他会滚不过去。
肥猪从小就很喜欢这样的一句谚语：猪往高处走，水往低处流，所以肥猪很喜欢凸起来的部分而不喜欢凹下去的部分。
现在肥猪可以把床中的某一些部分拿走，以让剩余部分所有凸起来的部分都是连起来的，这样肥猪就会很开心，因为他又可以滚来滚去了。
肥猪希望移除的部分最少
我们假设0表示某一个位置是凹下去的，1表示某一个位置是凸起来的。
那么
0
1
00111
01111000
11100
都是肥猪喜欢的钢琴床，因为所有凸起来的部分都是连续的
如果是
101
010011
1111101
就是肥猪不喜欢的钢琴床，因为所有凸起来的部分不是连续的
对于第一张床，肥猪可以把第二个位置拿走，这样床就变成了11。
对于第二张床，肥猪可以把第二个位置拿走，这样床就变成了00011。
输入描述
读入一共有两行，第一行只有一个正整数数n，表示钢琴床有n个部分。
第二行由一个01串组成
* n<=1000000
* 保证01串的长度为n
输出描述
输出一个正整数表示肥猪最少要拿走的部分的数量
示例1
输入:
10 0001111000
输出:
0
示例2
输入:
3 101
输出:
1
示例3
输入:
6 010011
输出:
1
C++(g++ 7.5.0) 解法, 执行用时: 29ms, 内存消耗: 2464K, 提交时间: 2022-11-11 08:53:07
#include<bits/stdc++.h>
using namespace std;
string s;
int tot1,tot2,n,tot,maxn=-1;
int main(){
cin>>n>>s;
for(int i=0;i<n;i++){
if(s[i]=='1')tot1++,tot++;
else tot2++;
if(tot2>=tot1){
tot1=tot2=0;
}
maxn=max(maxn,tot1-tot2);
}
cout<<tot-maxn;
}
C 解法, 执行用时: 7ms, 内存消耗: 1200K, 提交时间: 2021-09-28 17:42:08
#include<stdio.h>
int main()
{
int n,i,x=0,a=0,b=0;
char c[1000001];
scanf("%d",&n);
scanf("%s",c);
for(i=0;i<n;i++)
if(c[i]=='1') x++;
for(i=0;i<n;i++)
{
if(c[i]=='1') a++;
else a--;
if(a<0) a=0;
if(a>b) b=a;
}
printf("%d",x-b);
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 28ms, 内存消耗: 2468K, 提交时间: 2022-08-21 09:38:28
#include <iostream>
using namespace std;
int main(){
int n;
string a;
cin>>n>>a;
int t=0,p=0,m=0;
for(int i=0;i<n;i++){
if(a[i]=='1'){
t++;
p++;
}else{
p--;
}
if(p<0)p=0;
m=max(m,p);
}
cout<<t-m;
return 0;
}