HDU 5835 Danganronpa（弹丸论破）
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
| 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? | 雪染千纱是某学校的老师。她准备了许多礼物，共n种，每种a[i]件，在班会上发给学生。诸事繁杂，她只好把礼物交给班长千秋七海。由于学校设计神奇，学生的课桌只有一排。千秋七海希望如此安排礼物：
1.每张桌子都将准备一份神秘礼物和一份普通礼物。
2.为了彰显雪染千纱的大方，相邻桌子的普通礼物必须不同。
3.神秘礼物没有限制。
4.礼物必须连续发放。
她想知道最多有多少学生可以因此获得礼物（假设学生数量无限多）。作为她最重要的人，你必定对此问题手到擒来。 |
| 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). | 输入的第一行是一个整数 T(T≤10)表示测试用例的数量。
每个测试用例都有一个整数n。下一行有 n (1≤n≤10)个数: 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. | 对于每个测试用例，输出一行“Case #x: y”（没有引号），x表示测试用例的编号（从1开始）并且y表示七海千秋问题的答案。 |
| Sample Input - 输入样例 | Sample Output - 输出样例 |
| 123 2 | Case #1: 2 |
【题解】
水题，对礼物a[i]升序排序，求相邻没有相同种类礼物的排列长度（可横可竖），然后用最后若剩余礼物>前面长度，取前面长度，否则为 剩余礼物+(前面长度-剩余礼物)/2
【代码 C++】
1 #include2 #include 3 int data[15]; 4 int main(){ 5 int t, n, iT, i, s, opt; 6 scanf("%d", &t); 7 for (iT = 1; iT <= t; ++iT){ 8 printf("Case #%d: ", iT); 9 scanf("%d", &n);10 for (i = 0; i < n; ++i) scanf("%d", &data[i]);11 std::sort(data, data + n);12 for (i = s = 0; i < n - 1; ++i){13 s += data[i] << 1; data[i + 1] -= data[i];14 }15 if (data[i] < s) opt = data[i] + (s - data[i]) / 2;16 else opt = s;17 printf("%d\n", opt);18 }19 return 0;20 }