F. Teleporters-cf1661 F

F. Teleporters

https://codeforces.com/problemset/problem/1661/F

题意

一条路上0 \(a_1 a_2...a_{n}\)的位置上有传送门 要从x位置的传送门到y位置的传送门要花费\((x - y)^2\)
给定m 问从0位置到\(a_n\)位置 花费不超过m 最少需要再建多少个传送门

思路

对于一段区间 加进来k个传送门 那这k个传送门肯定是平均分配在这段区间上最优

我们想要花费不超过m的情况下 传送门增加得最少，
而我们可以发现一段区间每增加一个传送门花费就会减少一定量，而这个减少量会随着传送门增加的数量增大而减小
上面有个结论是增加量一定的情况下 最平均分配是最优的 那么我们就要让所有段即整体都平均
那么每一段的传送门对应的减少量应该一样
根据减少量 有二分性 我们可以二分那个减少量，找到某个减少量save 使得save的情况下花费小于等于m 但save+1的情况下花费大于m
然后根据减少量来确定每个段增加的传送门的数量 一段的减少量如果大于等于save 我们就可以给这个段加传送门 （计算每段传送门的数量也是用二分）

最后的得到的答案是相对优秀的 只是确定了减少量最大是多少
还要再减去(m-cost)/save 即还可以少增加多少个传送门

#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 5;
const int M = 5e5 + 5;
const ll mod = 998244353;

int n, a[N], d[N], ans, m;
int cnt, cost;

int cal(int k, int len){
	if(k > len) return len;
	int num = len / k;
	int res = len % k;
	return num * num * (k - res) + (num + 1) * (num + 1) * res;
}

bool check(int x){
	cnt = 0, cost = 0;
	//cerr << "??" << "\n";
	for(int i = 1; i <= n; i++){
		int l = 1, r = d[i];
		int ans = 1;
		while(l <= r){
			int mid = (l + r)>>1;
			if(cal(mid, d[i]) - cal(mid + 1, d[i]) >= x)
				ans = mid + 1, l = mid + 1;
			else r = mid - 1;
		}

		cnt += ans - 1;
		cost += cal(ans, d[i]);
		//cerr << l - 1 << " " << cnt << " " << cost << "\n";
	}
	return cost <= m;
}

void solve()
{
	cin >> n;
	int mx = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		d[i] = a[i] - a[i - 1];
	}
	cin >> m;

	int l = 0, r = 1e18;
	int save = 0;
	while(l <= r){
		int mid = (l + r)>>1;
		if(check(mid)) {
			l = mid + 1;
			save = mid;
		}
		else r = mid - 1;
	}

	check(save);
	//cerr << "save" << save << "\n";
	cnt -= (m - cost) / save;
	cout << cnt << "\n";
}


signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
}