首先我们定义“圈”为与原点距离相等的点集。
. . . 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;
}