自动搬运

查看原文

来自洛谷，原作者为

	Find_Yourself 竹杖芒鞋轻胜马，谁怕？一蓑烟雨任平生。

搬运于2025-08-24 22:31:48，当前版本为作者最后更新于2022-08-29 17:03:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先我们定义“圈”为与原点距离相等的点集。

. . . 3 . . .
. . 3 2 3 . .
. 3 2 1 2 3 .
3 2 1 0 1 2 3
. 3 2 1 2 3 .
. . 3 2 3 . .
. . . 3 . . .

暴力：

把圈放到堆里，然后每次取出代价最小的一圈，修改当前圈的楼层，向外圈拓展。

正解：

考虑二分。

如果是二分最终答案，我们会发现不好做，所以我们二分所有住户的代价的最大值，即 $c_i+dis \cdot t$（显然是具有单调性的）。

check 函数：由于圈的总数是 $\sqrt{n}$ 级别的，所以可以直接枚举，对于每一圈可以二分出楼层的最大值，然后增加住户总数，最后 return cnt >= n。

我们二分出可行与不可行的分界点，然后最终答案只需要在分界点的代价的基础上加上一些增量就行了。

具体看代码吧。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll n, t, k, c[N], sum[N], cnt = 0, ans = 0, a[N];
bool check(ll up) {
	cnt = 0; ans = 0;
	memset(a, 0, sizeof(a));
	for (ll i = 1;; ++i) {
		ll dis = (i - 1) * t;
		int p = upper_bound(c + 1, c + k + 1, up - dis) - c - 1; //二分出第i圈的最大楼层 
		if (p < 1) break;
		a[i] = p;
		ans += i * 4 * p * dis + sum[p] * i * 4;
		cnt += i * 4 * p;
		if (cnt >= n) return true;
	}
	return false;
}
int main() {
	ios::sync_with_stdio(false); cout.tie(0); cout.tie(0);
	cin >> n >> t >> k;
	for (int i = 1; i <= k; ++i) cin >> c[i], sum[i] = sum[i - 1] + c[i]; 
	ll l = 1, r = 1e18;
	while (r - l > 2) { //二分住户代价最大值 
		ll mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid;
	}
	ll up;
	for (ll i = r; i >= l; --i) {
		if (!check(i)) { //分界点 
			up = i + 1;
			break;
		}
	}
	int i, p;
	for (i = 1;; ++i) { //计算增量 
		ll dis = (i - 1) * t;
		p = upper_bound(c + a[i] + 1, c + k + 1, up - dis) - c - 1;
		if (p <= a[i]) continue; //不能写成break！ 
		if (cnt + i * 4 > n) break;
		ans += i * 4 * (c[p] + dis);
		cnt += i * 4;
	}
	ans += (n - cnt) * (c[p] + (i - 1) * t);
	cout << ans << endl;
	return 0;
}