ABC313

V_Melville精進録 / 2023-08-06 / 原文

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;
}