2007: Football Training Camp【原创-转载请说明】
Submit Page Summary Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 228 Solved: 30
Description
在一次足球联合训练中一共有n支队伍相互进行了若干场比赛。 对于每场比赛，赢了的队伍得3分，输了的队伍不得分，如果为平局则两支队伍各得1分。
Input
输入包含不超过1000组数据。 每组数据的第一行为一个整数n(2 ≤ n ≤ 20)，第二行为n个整数s1, s2, …, sn(0 ≤ si ≤ 200, 1 ≤ i ≤ n)，即各个队伍目前的得分。
Output
对于每组数据，用一行输出最少以及最多进行了多少场比赛，中间用一个空格隔开。 数据保证不会出现无解情况。
Sample Input
2
7 4
3
1 5 1
2
0 0
Sample Output
4 5
3 3
0 0
Hint
Source
湖南省第十三届大学生计算机程序设计竞赛
题解：比赛的时候陷在错误的思路里 其实这个题目真的水
每一场比赛如果是平局就总分增加2分 不然就加3分
所以要得到最多的比赛场次 就要优先平局
要得到最少的比赛场次 就要优先胜局
如果设置胜场的数目 如果总分为奇数 胜场数的下届就是1 不然就是0
因为如果是奇数 说明至少有一场是胜场
胜场数的上界就是 m
for(int i=0; i<n; ++i)
{
if(a[i]>=3)
m+=a[i]/3;
}
然后枚举胜场的场次 每一次增加2场胜场 保证剩下的总分是偶数
每一次枚举判断一下剩下的比分可不可以构成全是平局
如果可以的话 就说明这是一种符合情况的胜场次数
然后取符合情况中间 胜场最少的 和最多的 就是我们要求的答案了
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string.h>
#include<stack>
#include<queue>
using namespace std;
int a[];
int main()
{
int n,sum,m,ff,temp;
while(cin>>n)
{
int num1,num2;
ff=;
priority_queue<int ,vector<int > ,less<int> >que;
sum=;
m=;
while(!que.empty())
{
que.pop();
}
for(int i=; i<n; ++i)
{
scanf("%d",&a[i]);
sum+=a[i];
que.push(a[i]);
if(a[i]>=)
m+=a[i]/;
}
if(m==)
{
printf("%d %d\n",sum/,sum/);
continue;
}
if(sum%==)
{
ff=;
temp=que.top()-;
que.pop();
que.push(temp);
m--;
sum-=;
}
int flag=;
if((*que.top()<=sum))
{
num1=ff+sum/;
num2=ff+sum/;
flag=;
}
for(int i=; *i<=m; ++i)
{
temp=que.top()-;
que.pop();
que.push(temp);
temp=que.top()-;
que.pop();
que.push(temp);
sum-=;
if((*que.top()<=sum))//剩下的比分是否可以全部构成平局
{
num1=ff+*i+sum/;
if(flag==)
{
num2=ff+*i+sum/;
flag=;
} }
}
printf("%d %d\n",num1,num2);
}
return ;
}