来源：Codeforces Round 975 (Div. 2)

C. Cards Partition

题意

本身有 \(a_i\) 张 \(i\) 牌，现在将牌分成若干份，每一份牌数相等，且每一份都由不同的牌组成

同时有 \(k\) 次补充任意牌的机会，求最多分成一份几张牌

思路

假定分成 \(m\) 份，每份 \(p\) 张牌，那么所有牌加补充的牌等于\(m*p\)

同时，分成了 \(m\) 份说明每种牌不能超过 \(m\) 张，要不然用不完

那么根据 \(p\) 来枚举，\(p\) 最低为 \(1\)，最高为 \(n\)，再用牌的总数判断能否满足要求

代码

int solve() {
    int n, k;
    cin >> n >> k;
    int sum = 0;
    int mi = 0;
    rep(i, 0, n) {
        cin >> arr[i];
        sum += arr[i];
        mi = max(mi, arr[i]);
    }
  
    int ksum = sum + k;
    int ans = -1;
   
    for (int p = 1; p <= n; p++) {
        int m = ksum / p;
        // 分成的m份都要大于数组的最大值
        // 分成的m份和p大小，要在sum和sum+k中间
        if (m >= mi && m * p >= sum && m * p <= ksum) ans = p;
    }
    return ans;
}

E. Tree Pruning

题意

给树，要求每次减去叶子，让所有的叶子结点在同一层，求最少次数

思路

对于想让所有叶子结点在 \(k\) 层，比 \(k\) 深的子树需要减到 \(k\)，比 \(k\) 浅的需要剪到根

也就是说

1. 所有深度比deep深的结点都要减去
2. 所有子树深度比deep浅的结点都要减去

代码

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define rep(i, j, k) for (int i = (j); i < (k); i++)
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
const int N = 5e5 + 10;
vector<int> g[N];

int depth_cnt_sum[N];
int son_depth_cnt_sum[N];

int mxdep = 0; // 整棵树的最大深度

// 返回最深的儿子深度
int dfs(int i, int f, int dep) {
    depth_cnt_sum[dep]++;
    mxdep = max(mxdep, dep);

    int sonmxdep = dep;
    for (int j = 0, v; j < g[i].size(); j++) {
        v = g[i][j];
        if (v == f) continue;
        sonmxdep = max(sonmxdep, dfs(v, i, dep + 1));
    }
    son_depth_cnt_sum[sonmxdep]++;
    return sonmxdep;
}

void init(int n, int mx) {
    mxdep = 0;
    for (int i = 0; i <= mx; i++) {
        depth_cnt_sum[i] = 0;
        son_depth_cnt_sum[i] = 0;
    }
    for (int i = 1; i < n; i++) g[i].clear();
}

// 1. 所有深度比deep深的结点
// 2. 所有子树深度比deep浅的结点
int get(int deep) {
    return depth_cnt_sum[mxdep] - depth_cnt_sum[deep] + son_depth_cnt_sum[deep - 1];
}
void solve() {
    int n;
    cin >> n;
    rep(i, 0, n - 1) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0, 1);

    for (int i = 1; i <= mxdep; i++) {
        depth_cnt_sum[i] += depth_cnt_sum[i - 1];
        son_depth_cnt_sum[i] += son_depth_cnt_sum[i - 1];
    }
    int ans = 1e9;
    for (int deep = 1; deep <= mxdep; deep++) {
        ans = min(ans, get(deep));
    }
    cout << ans << endl;
    init(n + 1, mxdep);
}

int main() {
    IOS;
    int t;
    cin >> t;
    init(N, N - 1);
    while (t--) solve();
    return 0;
}