题意

一共 \(n\) 只球队，两两之间会进行一场比赛，赢得一分输不得分，给出每只球队最后的得分，问能否构造每场比赛的输赢情况使得得分成立。多组数据

\(T\le 10，n\le 5\times 10^4\)

分析

• 容易想到一个网络流的模型：把每场比赛看成点，连向对应的两只队伍。实际上可以把每只队伍的拆成 \(a_i\) 个点就是二分图的模型了。
• 考虑霍尔定理，队伍和队伍之间的区别只在于 \(a\) ，所以考虑枚举队伍数量 \(k\) ，判断最极端的 \(k\) 只队伍即可。\(a\) 最小的 \(k\) 只队伍应满足： \(\frac{k(k-1)}{2}\le \sum\limits_{i=1}^ka_i\)，所以排个序判断一下就好了。
• 总时间复杂度 \(O(nlogn)\)

代码

#include
    
     using namespace std;typedef long long LL;#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)#define rep(i, a, b) for(int i = a; i <= b; ++i)#define pb push_back#define re(x) memset(x, 0, sizeof x)inline int gi() {    int x = 0,f = 1;    char ch = getchar();    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}    while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}    return x * f;}template 
     
       inline void Max(T &a, T b){if(a < b) a = b;}template 
      
        inline void Min(T &a, T b){if(a > b) a = b;}const int N = 5e4 + 7;int n, T;int a[N];int main() {    T = gi();    while(T--) {        n = gi();bool fg = 1;LL tot = 0;        rep(i, 1, n) a[i] = gi(), tot += a[i];        if(tot != 1ll * n * (n - 1) / 2) {             puts("The data have been tampered with!");            continue;        }        sort(a + 1, a + 1 + n);        LL sum = 0;        rep(i, 1, n) {            sum += a[i];            if(1ll * i * (i - 1) / 2 > sum) { fg = 0; break;}        }        if(!fg) puts("The data have been tampered with!");        else puts("It seems to have no problem.");    }    return 0;}