首页 » 需要再看 » 正文

Football Training Camp

Football Training Camp

来源:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2007

Description

在一次足球联合训练中一共有n支队伍相互进行了若干场比赛。 对于每场比赛,赢了的队伍得3分,输了的队伍不得分,如果为平局则两支队伍各得1分。

Input

输入包含不超过1000组数据。 每组数据的第一行为一个整数n(2 ≤ n ≤ 20),第二行为 n 个整数 s1,  s2, …,  s n(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

湖南省第十三届大学生计算机程序设计竞赛

反思

好难受的一道题,开始分析最大的是否大于总数的一办,感觉总的所有的应该分析出来啦,下次找到数据看下哪错啦。
正解是:只要满足奇偶正确和最大的那个队的得分不高于其他所有的队伍之和,那么原先假设的平局匹配就是正确的,亏我还在想单独一个1,单独一个二多的时候该怎么办。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;  
int arr[100];  
const int INF = 0x7f7f7f7f;  
int main(){
    freopen("in.txt", "r", stdin);  

    int n, d;  
    while(~scanf("%d", &n)){
        priority_queue<int ,vector<int > ,less<int> >que;
        while(!que.empty())que.pop();  
        int m=0;  
        int sum =0;  
        for(int i=1;i<=n;i++){
            scanf("%d", &arr[i]);  
            que.push(arr[i]);  
            m += arr[i]/3;  
            sum += arr[i];  
        }
        int flag=0;  
        int ans1, ans2;  
        int ff=0;   
        if(sum % 2){ //最少需要一个胜 
            ff=1;  //至少需要1个
            int temp = que.top()-3;  
            que.pop();  
            que.push(temp);   
            sum -= 3;  
            m--;  
        }

        if(que.top() * 2 <= sum){//合法,其他的可以两两平局配对 
            ans1 = ff + sum/2;  
            ans2 = ff + sum/2;  //作为最初的
            flag=1;   
        }

        for(int i=1;i*2 <= m; i++){  //要想平衡,需要偶数个的少 
            int temp = que.top()-3;  
            que.pop();  
            que.push(temp);  

            temp = que.top()-3;  
            que.pop();  
            que.push(temp); 

            sum -= 6;  

            if(que.top()*2 <= sum){
                ans1 = ff + i*2 + sum/2;  
                if(!flag){
                    ans2 = ff + i*2 + sum/2;  
                    flag=1;  
                }
            }
        }

        printf("%d %d\n", ans1, ans2);  
    }
} 

赞 (0)

发表评论