526互联

Codeforces Round 680 (Div. 2, based on Moscow Team Olympiad) B. Elimination

发布时间 2023-10-13 16:29:42作者: zsxuan

一个比赛有一百人进入决赛，但是需要经过两轮初赛的选拔。初赛的最终结果由两场初赛产生，不幸的是初赛的最终排名被丢失了。

在每场初赛中，参赛者的排名按非升序排序。当两位参赛者的成绩一样，参赛编号更小的靠前。

现在只知道如下信息：

  • 第一场初赛中，第一百名的成绩为 \(a\) 。且第一场初赛中前一百名的选手在第二场初赛中至少取得了 \(b\) 的成绩。
  • 第二场初赛中，第一百名的成绩为 \(c\) 。且第一场初赛中前一百名的选手在第二场初赛中至少取得了 \(d\) 的成绩。

在两场初赛过后，所有参赛者按照两场比赛的成绩总分非升序排序，当成绩总分一样，按编号更小靠前。进入决赛的分数线是初赛最终排名第 \(100\) 名的总分。

给出 \(a, b ,c, d\) 。询问分数线最低可能是多少。

观察：第一场比赛中 \(rk100\) 的选手最低分数为 \(a + b\) ，第二场比赛中 \(rk100\) 的选手最低分数为 \(c + d\) 。这是唯一可以得到的信息。

显然有：第一场初赛中 \(rk100\) 最坏会排到 \(rk200\) ，第二场初赛中 \(rk100\) 最坏会排到 \(rk200\) 。于是最坏情况下 \(rk199 = max(a + b, c + d)\) ， \(rk200 = min(a + b, c + d)\) 。

假设最低分数线为 \(k\) ，显然 \(rk1 \sim rk198\) 的成绩都为 \(k\) 可以使得 \(rk100\) 的分数线最低。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int a, b, c, d; std::cin >> a >> b >> c >> d;
	std::cout << std::max(a + b, c + d) << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}

顺带有，\(rk1 \sim rk198\) 的成绩都为满分可以使 \(rk100\) 的分数线最高。