T1：To Be Saikyo
\(x \geqslant \max({p_i}), i > 1\)
代码实现
n = int(input())
a = list(map(int, input().split()))
if n == 1:
exit(print(0))
mx = max(a[1:])
ans = max(0, mx+1-a[0])
print(ans)
T2：Who is Saikyo?
对 \((A_i, B_i)\) 连一条有向边，使得 \(A_i \to B_i\)，同时统计每个点的入度
当入度为 \(0\) 的点超过 \(1\) 个则无解
否则答案为入度为 \(0\) 的那个点
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, m;
cin >> n >> m;
set<int> st;
for (int i = 1; i <= n; ++i) st.insert(i);
rep(i, m) {
int a, b;
cin >> a >> b;
st.erase(b);
}
if (st.size() >= 2) puts("-1");
else cout << *st.begin() << '\n';
return 0;
}
T3：Approximate Equalization 2
注意到不管怎么操作总和始终不变
最终的形态经排序后为 \((X, X, \cdots, X+1, \cdots, X+1)\)
总和 \(S = NX+r\)，其中 \(r\) 表示序列中 +1 的个数
那么 \(X = \lfloor\frac{S}{N}\rfloor\)，\(r = S\%N\)
然后将最终形态的序列和原序列作差，对差值为正数的那些数进行累加便能得到答案
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> a(n);
rep(i, n) cin >> a[i];
ll s = reduce(a.begin(), a.end());
ll x = s/n, r = s%n;
vector<ll> b(n, x);
rep(i, r) b[i]++;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
ll ans = 0;
rep(i, n) ans += abs(a[i]-b[i]);
ans /= 2;
cout << ans << '\n';
return 0;
}