题目重现

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?

输入格式

The first line of input contains an integer T($T le 10$) indicating the number of test cases.

Each case contains one integer n. The next line contains n ($1le n le 10$) numbers: $a_1, a_2, ..., a_n$, ($1 le a_i le 100000$).

输出格式

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.

样例输入

1
2
3 2

样例输出

Case #1: 2

题解

有n种礼物，每种礼物有a[i] 个。

每个礼物可以被包装成普通礼物或者神秘礼物（仅仅是包装的区别）。

要把这些礼物连续分配给若干人，每个人都要收到一个普通礼物与一个神秘礼物，相邻两人的普通礼物不能相同，但神秘礼物没有限制。

问最多能分配给多少人。

贪心，策略为：每次选取一个与上一个不同的并且剩余数量最多的礼物。

因为每个人有两个礼物，所以最终的人数的两倍一定小于等于礼物总数。

参考代码

• 优先队列 std::priority_queue

最后

以上就是自然短靴为你收集整理的CCPC(NQ)2016 - 1004 - Danganronpa 弹丸论破题目重现题解参考代码的全部内容，希望文章能够帮你解决CCPC(NQ)2016 - 1004 - Danganronpa 弹丸论破题目重现题解参考代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。