题解 P7640 [BalticOI 2006 Day 2] CITY PLANNING

· · 题解

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

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