A.BA 100pts
开场 \(3min\) 先打了个假做法向上取整求平均数，细看看到了 一张饼一个单位时刻只能在一张烙板上 这句话，重新想，困得要死，\(40min\) 才做完。
题意：
现在有 \(n\) 块烙板，\(m\) 张饼，第 \(i\) 张饼有 \(a_i\) 个面。
烙板一单位时刻可以烙熟一个面，一张饼一个单位时刻只能在一张烙板上，问都烙熟所需最少时间。
正解：
因为上文那句话的限制所以不能直接求总面数除以烙板数（向上取整）求平均数，根据该限制我们可以得到需要的时间至少为一张饼最多的面数（设为 \(t\) ）。
那么我们先假设答案为 \(t\)，此时可以理解为是面数最多的那张饼自己占了一个烙板 \(t\) 个时间，那么判断剩下 \((n-1)\) 张饼在 \(t\) 个时间内用 \((m-1)\) 个烙板是否可以完全烙熟。
这 \((n-1)\) 张饼中任意一张的面数都是小于等于 \(t\) 的，所以不再受那句话来限制，可以直接算 \((n-1)\) 张饼的总面数与 \((m-1)\) 作比，结果小于等于 \(t\) 则满足要求，答案为 \(t\)；否则 \(t\) 不够用。
\(t\) 不够用的时候，我们算一下 \(t\) 时间内没烙到的面数与总烙板数 \(m\) 的比值，加上 \(t\) 即为答案。
code：
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 10;
int n, m, a[N], cnt[N];
int main(){
// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n>>m; ll sum = 0;
for(int i=1; i<=n; i++){
cin>>a[i]; sum += a[i];
}
sort(a+1, a+1+n);
if(n <= m) cout<<a[n];
else{
if(sum - a[n] < (ll)a[n] * (m - 1)) cout<<a[n];
else{
sum -= (ll)a[n] * m;
cout<<(sum+m-1)/(ll)m+a[n];
}
}
return 0;
}
B.BB 5pts
题意：
luv...
正解：
见官方题解：
排序后 A 和 B 按排序一人取一个，算 A 的话，就是隔一个取一个。
code：
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int n, w[N], A;
int dep[N], size[N];
ll val[N];
vector<int>to[N];
void dfs(int rt, int p){
dep[rt] = dep[p] + 1, size[rt] = 1;
for(int i=0; i<to[rt].size(); i++){
int y = to[rt][i];
dfs(y, rt);
size[rt] += size[y];
}
val[rt] = size[rt] - dep[rt] - w[rt];
}
int main(){
// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++) cin>>w[i];
for(int i=2; i<=n; i++){
int p; cin>>p;
to[p].push_back(i);
}
dfs(1, 0);
sort(val+1, val+1+n);
ll ans = 0;
for(int i=n; i>=1; i-=2){
ans += val[i];
}
cout<<ans;
return 0;
}