D题题解

比赛时候弄错了一行代码，一直没AC，吐血。。。
直接贪心，从后往前翻，只要出现连续两个1就进行翻转，这样就能确保收益大于直接修改的，具体细节看代码（不过好像dp的方法比较无脑，贪心的细节容易错，好吧，还是太菜了）

记录修改的位置，通过二分查找判断每个点在翻转完毕以后是1还是0，如果是1就需要修改。

#include <bits/stdc++.h>
using namespace std;
int a[100100],pre[100100];
int loc[100100];
int lian0[100100],lian1[100100];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==0)
        {
            if(a[i-1]!=0) lian0[i]=1;
            else lian0[i]=lian0[i-1]+1;
            lian1[i]=0;
        }
        else if(a[i]==1)
        {
            if(a[i-1]!=1) lian1[i]=1;
            else lian1[i]=lian1[i-1]+1;
            lian0[i]=0;
        }
    }
    //for(int i=1;i<=n;i++) cout<<lian0[i]<<" "<<lian1[i]<<endl;
    bool flag=true;
    int cnt=0;
    int top=0;
    for(int i=n;i>=1;i--)
    {
        if(flag&&lian1[i]>1&&a[i]==1)//翻转
        {
            loc[top++]=i;
            cnt++;
            flag=false;
        }
        else if(flag==false&&lian0[i]>1&&a[i]==0)//翻转
        {
            loc[top++]=i;
            cnt++;
            flag=true;
        }
    }
    reverse(loc,loc+top);
    //for(int i=0;i<top;i++) cout<<loc[i]<<" ";
    for(int i=1;i<=n;i++)
    {
        int p=lower_bound(loc, loc+top, i)-loc;
        p=top-p;
        //cout<<i<<"-p:"<<p<<endl;
        if((p&1)==1&&a[i]==0)
        {
            cnt++;
            //cout<<"i:"<<i<<endl;
        }
        else if((p&1)==0&&a[i]==1)
        {
            cnt++;
            //cout<<"i:"<<i<<endl;
        }
    }
    printf("%d\n",cnt);
}