526互联

The 2nd Universal Cup. Stage 6: Warsaw L.Spectacle （思维）

发布时间 2023-10-23 21:21:21作者: qdhys

大致题意：

  给定n个玩家，每个玩家有一个战力值，安排 x (1 <= x <= n/2（向下取整))场游戏，每场游戏安排x对玩家对战，对于每一场游戏每个玩家只能参加一次对战，要求对于每x场玩家对战的两个玩家rating差的最大值尽可能小。

  例如给定6个玩家战力值为10 13 14 20 100 105，当x = 1的时候我们选择战力值为13 和 14的玩家进行对战最优，当x = 2的时候，我们选择13 和 14对战， 100和105对战最优（也可以是10 和 13对战， 100 和 105对战等等）

解题思路

  将玩家的rating排序后，可以发现这么个性质:一定是选择排完序之后的相邻玩家进行对战最优，因为他们的差值最小。

  所有的相邻玩家有n-1个差值，将这些差值和每个差值对应的两个下标提取出来按照差值进行排序，叫做rank数组，里面存储差值和差值对应的两个下标。下标从1开始。那么当我们统计x = 1的答案的时候，rank[1]里面存储的差值就是x = 1的时候的答案。

  那么当x = 2的时候，rank[2]里面的差值就是答案吗?

  稍加思考我们会发现并不是，如果有这种情况，rank[1]里面的两个下标为2和3，此时我们rank[2]里面存储的两个下标恰巧是3和4，如果我们要用下标3和下标4进行对战，那么下标2和下标3就不能进行对战。

  那么再思考如果rank[3]里面的下标恰巧是1和2的话，现在x = 2的答案会出现吗？

  会。此时我们让下标1和下标2对战，下标3和下标4对战。因为我们是按照差值大小排序的，那么x = 2的答案就是rank[3]里面存储的差值。这个时候可能就有人会想（其实是我自己会想）那我如何判断什么时候要拆开先前的组成的一对玩家换成遍历到的玩家进行对战呢。如果当前是要x-1和x打，在此之前我还存在这样的下标对战：1打2,2打3,3打4...，x-2打x-1，我又该如何抉择呢？

  其实很简单，我们只需要对先前遍历到玩家的时候，将他们丢进并查集，此时只要是两个大小为奇数的并查集进行合并，那么答案就会出现。

  假设在遍历到ranp[k]的时候x-1和x对战的时候已经存在1，2，3...，x-2这么一个集合。还存在x，x+1，x+2...这么一个集合。如果左边集合的大小为奇数，右边集合的大小为奇数，此时合并的话集合大小为偶数，而且这个合并完的集合我们可以让1和2对战,3和4对战...，此时答案就是rank[k]里面的差值。至于为什么，因为其他玩家对战的差值一定小于等于rank[k]里面的差值。如果左边集合大小为奇数右边集合大小为偶数很显然对战场数不会增加。很显然如果两个集合的大小是偶数也不会改变对战场次。

#include <bits/stdc++.h>

const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
using ll = long long;
typedef std::pair<ll, ll> PII;
typedef std::array<int, 3> a3;
#define ls u << 1
#define rs u << 1 | 1

int n, m;

long long a[N];
long long ans[N];

int father[N], sz[N];

inline int findset(int x) {
	return x == father[x] ? x : father[x] = findset(father[x]);
}

inline void solve() {
	std::cin >> n;

	for (int i = 1; i <= n; i ++) std::cin >> a[i];
	
	for (int i = 1; i <= n; i ++) father[i] = i, sz[i] = 1;

	std::sort(a + 1, a + n + 1);
	
	std::map<ll, std::vector<PII>> mp;
	for (int i = 2; i <= n; i ++)
		mp[a[i] - a[i - 1]].push_back({i - 1, i});
	
	int turn = 0;
	for (auto x: mp) {
		auto val = x.first;
		auto &tmp = x.second;
		for (auto &[x1, y1]: tmp) {
			x1 = findset(x1), y1 = findset(y1);
			father[x1] = y1;
			if ((sz[y1] & 1) && (sz[x1] & 1)) 
				ans[++ turn] = val;
			sz[y1] += sz[x1]; 
		}
	}
	
	for (int i = 1; i <= n / 2; i ++) std::cout << ans[i] << ' ';
}

int main(void) {
   std::ios::sync_with_stdio(false);
   std::cin.tie(0);
   std::cout.tie(0);
   
   int _ = 1;
   //std::cin >> _;
   while (_ --) solve();
   
   return 0;
}