2017 湖南省赛 K Football Training Camp

题意:

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

现在给出每只队伍的得分$s_i$,问最少和最多进行了多少场比赛，不超过1000组数据

$1<=n<=20$

$0<=s_i<=200$

思路：

比赛的时候脑子不清醒，被这个配对难住了，暴力往搜索方面想了想，肯定会TLE啦，就放弃了

现在清醒一点，胜负局对胜负配对没有影响，只有平局对配对有影响，而且平局越多，比的场次也越多

如果设胜负局有$x$场，平局$y$场，则有$3x + 2y = sum$

枚举$x$, 判断是否可以出现$y$场平局,但是这里取胜的队伍策略不固定，所以不好判断平局是否可以出现

现在问题就变成给一个局面如何判断当前局面，可以全打平局

当且仅当 $sum$ 为偶数, 且$max <= sum / 2$

$sum$为偶数是显然的,若$max > sum / 2$, 那么剩下的数无法消除$max$

考虑这样一种方法，假设$a_1,a_2,...a_n$为得分从小到大排序后的序列,找到中线所在的位置

令$psum[i]$为分数的前缀和,假设$i$为一个满足 $psum[i-1] + a_i >= sum / 2$的位置

若$psum[i-1] + a_i = sum / 2$ 显然就可以将$a_1,...a_i$和$a_{i+1},...a_n$这两部分配对即可

若$psum[i-1] + a_i > sum / 2$ 这样将$a_i$分成了两部分,将左边部分$sum / 2 - psum[i-1]$用$a_{i+1},...a_n$消掉,右边部分$psum[i] - sum / 2$用$a_1,...a_i$消掉

然后$a_{i+1},...a_n$ 与 $a_1,...a_i$配对即可

这样若$max > sum / 2 $那么中线一定会出现在 $a_n$ 中，就无法成功配对了。

知道了这个结论，现在只需要每次贪心将$max$ 取一场胜负局，再接着判定平局是否合法即可

#include<queue>

#include<algorithm>

#include<iostream>

#include<cstdio>

#define LL long long

using namespace std;

priority_queue<int > q;

int main(){

    int n;

    while(scanf("%d",&n) == 1){

        int x,ansmx = 0,ansmi = 0;

        while(!q.empty()) q.pop();

        int sum = 0;

        for(int i = 1;i <= n;i++){

            scanf("%d",&x);

            q.push(x);

            sum += x;

        }

        int cnt = 0;

        while(!q.empty()){

            x = q.top();q.pop();

            if(sum % 2 == 0 && x <= sum / 2) {

                if(!ansmx) ansmx = cnt + sum / 2;

                ansmi = cnt + sum / 2;

            }

            if(x < 3) break;

            sum -= 3;

            q.push(x - 3);

            cnt++;

        }

        cout<<ansmi<<" "<<ansmx<<endl;

    }

    return 0;

}