526互联

Educational Codeforces Round 152 (Rated for Div. 2) D. Array Painting

发布时间 2023-08-01 19:09:26作者: 突破铁皮

初始所有点都是蓝色的，给定一个数组，每个元素为0，1，2等值，两种操作，选定一个点花1元变红，或者选定一个为1或者2的红色点，减去一个价值，让周围的点变红，最后所有点都要变红

思路：贪心，对于一个数组来说我们找寻连续的不等于0的一段，判断每一段最多所能变红的

存在两种情况

010，这种情况花1可以最多变红两点

020，花1三点全变红

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int N=2e5+10;
int a[N];
int n,t;
bool flag[N];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int sum=0;
	memset(flag,0,sizeof flag);
	for(int i=1;i<=n;i++){
		if(a[i]!=0){
			bool f=0;//判断是否有2
			flag[i]=1;
			if(flag[i-1]||i==1) f=1;//对于全是1的点只能选择一边，如果左边已经被之前标记了则这次标记右边
			if(a[i]==2) f=1;
			int j=i+1;
			while(j<=n&&a[j]) flag[j]=1,f|=a[j]==2,j++;
			i=j;
			if(!f) i--;
			else flag[j]=1;
			sum++;
		}
		else if(a[i+1]==0){
			sum++;
		}
	}
	cout<<sum<<endl;
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //cin>>t;
    t=1;
    while(t--){
	solve();
}
}