58同城 01序列 贪心

题目描述

给定一个数组metrix，数组中只包含1和0，且数组中的1都不相邻，输入一个数n，问能否在将数组中n个0替代换成1后不破坏1都不相邻的条件。
例1 metrix=[1,0,0,0,1],n=1输出true
例2 metrix=[1,0,0,0,1],n=2输出false

输入描述:

输入一个数m(1≤m≤100000)表示metrix的长度第二行m个数 0或1 表示改位置数组中的元素是0还是1第三行输入一个数n

输出描述:

输出true或false

示例1

输入

5
1 0 0 0 1
1

输出

true

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
int main()
{
    int n,num;
    while(cin>>n)
    {
        for(int i=0;i<n;++i) cin>>arr[i];
        cin>>num;
        int cnt=0,sum=0;
        for(int i=0;i<n;++i)
        {
            if(arr[i])
            {
                sum+=(cnt-1)/2;
                cnt=0;
            }else 
            {
                cnt++;
            }
        }
        sum+=(cnt-1)/2;
        //cout<<sum<<endl;
        if(num<=sum)
        {
            cout<<"true"<<endl;
        }else cout<<"flase"<<endl;
        
    }
    return 0;
}