|
|
вернуться в форумWhat's wrong! I think it was so easy, but what's wrong on my program? #include<iostream.h> int N; int how[21]; int total; void main() { int i, j, max, pos, hints, sum; cin>>N; total=0; for (i=0; i<N; i++) { cin>>how[i]; total+=how[i]; } if (N<=3) { cout<<0; return; } max = 1; hints=0; while ( total>0 ) { max = 0; pos =-1; for (i=0; i<N; i++) { sum = 0; for (j=0; j<3; j++) sum += how[(i+j)%N]; if (sum>max) { pos=i; max=sum; } } if ( pos < 0 ) break; for (j=0; j<3; j++) how[(pos+j)%N]=0; total -= max; hints+=total; } cout<<hints<<endl; } Re: What's wrong! Your algorithm is incorrect. Consider the following test case: 7 6 6 6 7 5 1 1 Your algorithm will remove the middle (6 6 7) first, then remove the end (1 1 6), thus incurring a total of 13 + 5 = 18 damage. The correct solution is to remove the start (6 6 6) first, then remove (7 5 1), thus incurring a total of 14 + 1 = 15 damage. |
|
|