394

# 题目

## 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.

1. In order to reflect the Chisa Yukizome's generosity, the kinds of the ordinary gift on the adjacent table must be different.

1. There are no limits for the mysterious gift.

1. 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.

1
2
3 2

Case #1: 2

# 题解

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

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

(用 <span style="color: rgb(187,224,227)">青色</span> 表示最多的一种礼物, <span style="color: rgb(146,208,80)">绿色</span> 表示其他所有礼物)

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

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

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

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

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

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

# 代码

/*
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;
}

• 点击查看/关闭被识别为广告的评论