「模拟赛」暑期集训CSP提高模拟14（8.6）

yuen_blog / 2024-08-08 / 原文

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

原题 THUPC 2023

题意：

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