IMO, version 1 better than version 2, version 2 better than version 3.
make some preprocess to make you code simple and efficient. Here divide the input by 2, so you don’t have to do dividsion on each loop.
version 1 is best
thanks to
http://www.cnblogs.com/kuangbin/archive/2012/06/03/2532690.html
#include <cstdio>
#include <algorithm>
#define MAXSIZE 10000
int candies[MAXSIZE];
int main() {
//freopen("input.txt","r",stdin);
int n, cnt_whistle, i, tmp;
while(scanf("%d",&n)!=EOF && n>0) {
for(i=0;i<n;++i) { scanf("%d",&tmp); candies[i]=tmp>>1; }
for(--n, cnt_whistle=1;;++cnt_whistle) {
tmp=candies[n];
for(i=n;i>0;--i) {
candies[i]=(candies[i-1]+candies[i]+1)>>1;
}
candies[0]=(tmp+candies[0]+1)>>1;
for(i=1;i<=n && candies[i-1]==candies[i];++i) ;
if(i-n==1) break;
}
printf("%d %d\n",cnt_whistle,candies[0]<<1);
}
return 0;
}
use division’s floor property (5/2=2) to avoid if sentences. in version 2 here
t2=candies[i];
candies[i]=(t1+t2+1)>>1;
t1=t2;
if don’t divide input by 2, the code will be
t2=candies[i]>>1;
candies[i]=t1+t2;
if(candies[i]%2) ++candies[i];
t1=t2;
how to avoid process the border conditions? version 2 better than version 3 on this aspect. version 1 accomplish this, thanks to
http://www.acmerblog.com/hdu-1034-candy-sharing-game-1285.html
version 2
#include <cstdio>
#include <algorithm>
#define MAXSIZE 10000
int candies[MAXSIZE];
int main() {
//freopen("input.txt","r",stdin);
int n, cnt_whistle, i, t1,t2;
while(scanf("%d",&n)!=EOF && n>0) {
for(i=0;i<n;++i) { scanf("%d",&t1); candies[i]=t1>>1; }
for(--n, cnt_whistle=1;;++cnt_whistle) {
t1=candies[n];
for(i=0;i<=n;++i) {
t2=candies[i];
candies[i]=(t1+candies[i]+1)>>1;
t1=t2;
}
for(i=1;i<=n && candies[i-1]==candies[i];++i) ;
if(i-n==1) break;
}
printf("%d %d\n",cnt_whistle,candies[0]<<1);
}
return 0;
}
version 3
#include <cstdio>
#include <algorithm>
#define MAXSIZE 10000
int candies[MAXSIZE];
int cand_temp[MAXSIZE];
int main() {
//freopen("input.txt","r",stdin);
int n, cnt_whistle, i, *p,*q;
while(scanf("%d",&n)!=EOF && n>0) {
for(i=0;i<n;++i) { scanf("%d",&t1); candies[i]=t1>>1; }
p=candies, q=cand_temp;
for(--n, cnt_whistle=1;;++cnt_whistle) {
for(i=1;i<=n;++i) {
q[i]=(p[i-1]+p[i]+1)>>1;
}
q[0]=(p[n]+p[0]+1)>>1;
std::swap(p,q);
for(i=1;i<=n && p[i-1]==p[i];++i) ;
if(i-n==1) break;
}
printf("%d %d\n",cnt_whistle,p[0]<<1);
}
return 0;
}
p.s. when you use swap tricks (as in version 3), be careful with the check points, e.g. the initialization part, the conclusion part, especially the items are used by multiple times.
here is mistake I made, 1st, initilization error
position of
cnt_whistle=1;
mistakely put it to declaration part rather than just befor the for loop;
2nd, the third parameter of printf
mistakely wirite
printf("%d %d\n",cnt_whistle,candies[0]<<1);
which should be
printf("%d %d\n",cnt_whistle,p[0]<<1);
版权声明:本文为博主原创文章,未经博主允许不得转载。// p.s. If in any way improment can be achieved, better performance or whatever, it will be well-appreciated to let me know, thanks in advance.