2021杭电暑假多校9_1010.Unfair contest（分类讨论）

本文主要是介绍2021杭电暑假多校9_1010.Unfair contest（分类讨论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1010.Unfair contest

题目大意：

意思是总共 $n$ 个裁判，裁判要求打分区间在 $[1, h]$ 内，同时你已经知道前 $n - 1$ 个裁判对AB两人的打分 $a_1,a_2,a_3...a_n-_1；b_1,b_2...b_n-_1；$ ，比赛评价机制是总分去掉 $s$ 个最高分再去掉 $t$ 个最低分后的总和比较。你希望A胜利，但又不希望太明显，所以会想办法在让A能赢的情况下让 $a_n-b_n|$ 尽可能小。

思路：

请添加图片描述
第三种情况中，差值原本只是sumb-suma。但是在两种特殊情况下，差值需要特取。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
ll a[maxn], b[maxn];int main() {int T;scanf("%d", &T);while (T--) {int n, s, t;ll h;scanf("%d%d%d%lld", &n, &s, &t, &h);n--;for (int i = 1; i <= n; i++) {scanf("%lld", &a[i]);}for (int i = 1; i <= n; i++) {scanf("%lld", &b[i]);}sort(a + 1, a + n+1);sort(b + 1, b + n+1);a[n + 1] = h;b[n + 1] = h;b[0] = 1;a[0] = 1;//对于 s = 0 以及 t = 0 特判//al=suma+a[0],ar=suma+a[n+1];//可以证明是特判处理是正确的。ll suma=0,sumb=1;for(int i=t+1;i<=n-s;i++)suma+=a[i],sumb+=b[i];ll al=suma+a[t],ar=suma+a[n-s+1];ll bl=sumb+b[t],br=sumb+b[n-s+1];if(ar<bl)printf("IMPOSSIBLE\n");else if(al>=br)printf("%lld\n",1-h);else{ll tmp=0;if(al>=bl)tmp=max(tmp,a[t]-1);if(ar>=br)tmp=max(tmp,h-b[n-s+1]);printf("%lld\n",sumb-suma-tmp);}}
}