描述
牛一行20他们喝的水碗。碗可以那么(面向正确的为清凉水)或颠倒的(一个位置而没有水)。他们希望所有20个水碗那么,因此用宽鼻子翻碗。
嘴太宽,他们不仅翻转一碗还碗的碗两侧(总共三个或三个——在两端的情况下碗——两碗)。
给定的初始状态碗(1 =不能饮用的,0 =饮用——它甚至看起来像一碗),什么是必要的最小数量的碗翻转将所有的碗那么?
输入
1号线:一行20空格分隔的整数
输出
线路1:所需的最小数量的碗翻转翻碗那么(即。0)。对于给定的输入,它总是可以找到一些组合的翻转操作碗20 0。
样例输入
0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0
样例输出
3
提示
解释的样本:
翻转碗4,9岁和11岁时让他们饮用:
0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0(初始状态)
0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0(后翻碗4]
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0翻碗后[9]
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0翻碗后[11]
思路：
分别从左右两边开始，找到为1 的位置，让后两个取反；不可能出现最后位置或首位置翻到最后扔为1；所以当这种情况出现就赋大值给计数器并终止
循环；最后取左右两计数器的最小值
#include<cmath> #include<iostream> using namespace std ; int main () { int cnt1=0,cnt2=0; int a[20],b[20]; for(int i=0;i<20;i++) { cin>>a[i]; b[i]=a[i]; } for(int i=0;i<20;i++) { if(a[i]==1) { if(i==19) {cnt1=20; break; } cnt1++; a[i+1]=!a[i+1]; a[i+2]=!a[i+2]; } } for(int i=19;i>=0;i--) { if(b[i]==1) { if(i==0) { cnt2=20; break; } cnt2++; b[i-1]=!b[i-1]; b[i-2]=!b[i-2]; } } cout<<min(cnt1,cnt2)<<endl; return 0; }