[hdu5503]EarthCup[霍尔定理]

题意

一共 \(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<bits/stdc++.h>

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 <typename T> inline void Max(T &a, T b){if(a < b) a = b;}

template <typename T> 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;

}

巴特西

[hdu5503]EarthCup[霍尔定理]

题意

分析

代码

最新文章

热门文章