题目

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

题解

给同学发礼物,共有 n 种礼物,其中第 i 种礼物有 a[i] 个礼物分为两种

  • 普通礼物:相邻两个人的普通礼物不能相同
  • 神秘礼物:可以和普通礼物相同,不做任何限制

任何一个礼物都可以做普通礼物或者神秘礼物

根据上面的要求,显然限制只有普通礼物,可以先考虑普通礼物的问题
先在只考虑普通礼物的情况下尽可能的多分,计算能分多少组
假设结果为 ans ,礼物总数为 sum

  • 如果 ans 比 sum/2 还大,证明普通礼物的限制已经无法阻挡发礼物了~
    因此结果应该是 sum/2 (每个人至少需要两个礼物)
  • 如果 ans 没有 sum/2 大,那么说明普通礼物的限制导致最多只能发给 ans 个同学
    剩下的礼物中随便拿 ans 个当作神秘礼物发放即可

根据上面的分析,可以得出: 只需要计算出所有礼物中排列后不连续能达到多长,将答案记为 ans ,则最后答案就是 min(ans,sum/2)

问题转化成:
有 n 种礼物,每种有 a[i] 个,相邻不相同,最多能有多少个

排列不相邻 可以很容易想到数学中 排列组合 的 插值法

插值的意思是先将一些相同元素排列好,然后在每两个中间插入另一种元素,这样就能保证所有元素相邻的元素都不相同
完成插值第二种元素至少只能比第一种元素少 1 (参考下面的图)

因此,需要先对所有礼物排序,从最多的开始判断
有两种情况:
(用 青色 表示最多的一种礼物, 绿色 表示其他所有礼物)

  • 最多的元素不到礼物总数的一半


    由于最多的元素不到礼物总数的一半,因此剩下的元素必然满足 大于等于最多的元素
    也即,绿色元素必定能够将所有的青色元素分割开

    根据 贪心 ,要满足尽可能多插,就要从多往少插
    按照上面的解释,已经可以保证在将青色元素分隔开后,相邻元素必然是不相同的
    剩下的礼物不管有多少个,必然会有一个和它不同,并且比它多的另一种礼物
    只需要将其插到这个比它多的礼物中即可

    所有的礼物都可以被按照要求排序
    这种情况下 ans = sum

  • 最多的元素超过了礼物总数的一半


    这种情况下,青色的元素都不能被分隔开
    最多只能有红框内的区域能够分割开

    这种情况下 ans = (sum-a[n-1])*2 + 1

得到 ans 后,结果就应该是 min(ans,sum/2)

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリ0隶�
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <bitset>
#include <iomanip> 
using namespace std;

const int maxn = 15;
int a[maxn];

void Do() {
    int n;
    cin >> n;
    int sum = 0;
    for(int i = 0;i < n;i++) {
        cin >> a[i];
        sum += a[i];
    }
    sort(a,a + n);
    int ans = 0;
    if(sum / 2 < a[n - 1]) {
        ans = (sum - a[n - 1]) * 2 + 1;
    } else {
        ans = sum;
    }
    cout << min(ans,sum / 2)<<endl;

}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);
    int T;
    cin >> T;
    for(int i = 1;i <= T;i++) {
        cout << "Case #" << i << ": ";
        Do();
    }
    return 0;
}