22. CF-Teleporters

题目链接：Teleporters

题目给的这 \(n\) 个区间都是固定的，可以一个个分开来考虑。对于一个区间，如果新增 \(k-1\) 个传送门将其分为 \(k\) 个子区间，显然最优的放法是尽可能平均的放置。

我们的目标是最小化新增的传送门数量，使费用不超过 \(m\)，所以我们希望每次新放的传送门都能尽可能的多节省一些费用。在一个区间内新增一个传送门所节省的费用可以 \(O(1)\) 计算。在一个区间内，随着传送门数量的增加，每次新增所能节省的费用会逐渐减少。那么我们可以二分这个节省的费用 \(cost\)，只要往一个区间里加传送门节省的费用 \(\ge cost\)，就继续增加，这可以固定 \(cost\) 后二分门的数量来算。如果最后多省下了一些费用，再计算出可以去掉的传送门数量，减一下就是答案了。

#include 
using namespace std;
using ll = long long;
using pll = pair;
#define endl '\n'
const int maxn = 2e5 + 5;
int n;
ll a[maxn];
ll calc(ll dis, ll seg) {
    ll x = dis % seg, y = seg - x, v = dis / seg;
    return y * v * v + x * (v + 1) * (v + 1);
}
pll check(ll save) {
    ll cost = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) {
        ll d = a[i] - a[i - 1];
        ll l = 0, r = d, res = 1;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (calc(d, mid - 1) - calc(d, mid) >= save)
                res = mid, l = mid + 1;
            else
                r = mid - 1;
        }
        cost += calc(d, res);
        cnt += res - 1;
    }
    return {cost, cnt};
}
void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    ll m;
    cin >> m;
    ll l = 0, r = 1e18, save = 0;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        pll tmp = check(mid);
        if (tmp.first <= m)
            save = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    pll ans = check(save);
    ans.second -= (m - ans.first) / save;
    cout << ans.second << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}