浙江财经大学
信息管理与工程学院

HDU 5835 Danganronpa

本文由 Ocrosoft 于 2016-08-15 10:24:17 发表

Danganronpa

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 319    Accepted Submission(s): 228

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 (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
 

Author
UESTC
 

Source
题意:有n种礼物,每种礼物有a[i]个,每张桌子要求放一个神秘礼物和一个一般礼物,但是神秘礼物没有要求是哪种礼物,可以随便指定。问最多能放多少桌子。
思路:既然神秘礼物没有指定,那么就可以随便选。每张桌子分别放一个最多一个最少的礼物。
注:sum/2也能过,数据比较水,一种礼物的时候就会错。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const int INF = INT_MAX;
const int MAXN = 100000 + 10;
using namespace std;
int a[MAXN];
int main()
{
	int T, cas = 1;
	cin >> T;
	while (T--)
	{
		int n, sum = 0;
		cin >> n;
		for (int i = 0; i < n; i++)cin >> a[i], sum += a[i];
		sort(a, a + n);
		int i = 0, j = n - 1, ans = 0;
		while (i < j)
		{
			int minn = min(a[i], a[j]);
			ans += minn * 2;
			a[i] -= minn;
			a[j] -= minn;
			if (!a[i])i++;
			if (!a[j])j--;
		}
		printf("Case #%d: %d\n", cas++, min(ans, sum / 2));
	}
	//system("pause");
	return 0;
}

 

欢迎分享与转载,请保留链接与出处。Ocrosoft » HDU 5835 Danganronpa

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址