Question

ZOJ Problem Set - 1622 地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=622

感觉不是很难但是一直WA，不知道错哪里了，求大神指点
下面是我的代码
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int arrLight[10010];
int main()
{
int N;
//freopen("in.txt","r",stdin);
while(scanf("%d",&N)==1)
{
int sum = 0;
memset(arrLight,-1,sizeof(arrLight));
for(int k = 0; k < N ; k++)
cin>>arrLight[k];
if(N==1)
{
cout<<sum<<endl;
}
else
{
for(int i = 0 ; i < N ; i++)
{
if(arrLight[i]==arrLight[i+1])
{
arrLight[i+1] = !arrLight[i+1];
sum++;
}
}
cout<<sum<<endl;
}

}
return 0;
}
感觉不是很难但是一直WA，不知道错哪里了，求大神指点

Answer 1

你这样不对吧，应该枚举第1个是亮的还是暗的来做。这样的复杂度也是O(n)

追问

怎么个枚举法，你有A过这题么？

追答

假设第1个灯是亮的，然后做一次，假设第1个灯是暗的，做一次，两次结果取最小值。

没做过，但是题目只要求最后只要灯一亮一暗就行了，所以这样枚举是对的。

刚刚做了一下，AC了

#include
#include
const int MAX=11000;
int a[MAX];
int calc(int tag,int n)
{
int ret=0;
int i;
for(i=0;i<n;i++)
{
if(a[i]!=((i&1)^tag)&1)ret++;
}
return ret;
}
int main()
{
int n;
int i;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)scanf("%d",&a[i]);
int ans=calc(0,n);
int tmp=calc(1,n);
if(tmp<ans)ans=tmp;
printf("%d\n",ans);
}
return 0;
}

/*

*/