Danganronpa

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 0    Accepted Submission(s): 0 Problem Description Chisa Yukizome works as a teacher in the school. She prepares many gifts, which consist of  n  kinds with  a[i]  quantities of each kind, for her students and wants to hold a class meeting. Because of the busy work, she gives her gifts to the monitor, Chiaki Nanami. Due to the strange design of the school, the students' desks are in a row. Chiaki Nanami wants to arrange gifts like this: 1. Each table will be prepared for a mysterious gift and an ordinary gift. 2. In order to reflect the Chisa Yukizome's generosity, the kinds of the ordinary gift on the adjacent table must be different. 3. There are no limits for the mysterious gift. 4. The gift must be placed continuously. She wants to know how many students can get gifts in accordance with her idea at most (Suppose the number of students are infinite). As the most important people of her, you are easy to solve it, aren't you?   Input The first line of input contains an integer  T(T≤10)  indicating the number of test cases. Each case contains one integer  n . The next line contains  n   (1≤n≤10)  numbers:  a1,a2,...,an ,  (1≤ai≤100000) .   Output For each test case, output one line containing “Case #x: y” (without quotes) , where x is the test case number (starting from 1) and y is the answer of Chiaki Nanami's question.   Sample Input 1 2 3 2   Sample Output Case #1: 2

思路：

由于题目意思是对于普通礼物有要求，相邻两个座位不能是相同的礼物；那么我们就先分配好普通礼物；在分配普通礼物的人数尽可能多的情况下，考虑剩余的礼物数来分配神秘礼物。对于普通礼物分配，我们每次只需取两种不同的礼物间隔分就好！

AC代码如下：

#include <stdio.h> #include<algorithm> using namespace std; int main() { int i,j,t,n; int a[100]; scanf("%d",&t); for(i=1;i<=t;i++) { scanf("%d",&n); int tol=0; for(j=0;j<n;j++){ scanf("%d",&a[j]); tol+=a[j]; } int sum=0,last;last=a[0]; for(j=1;j<n;j++) { if(a[j]>=last){ sum+=last*2;last=a[j]-last;} else { sum+=a[j]*2;last-=a[j];} } if(tol>=sum*2) printf("Case #%d: %d\n",i,sum); else printf("Case #%d: %d\n",i,tol/2); } return 0; }