Teleporters（ Educational Codeforces Round 126 (Rated for Div. 2) ）

Teleporters（ Educational Codeforces Round 126 (Rated for Div. 2) ）

There are $n+1$ teleporters on a straight line, located in points $0$, $a_1$, $a_2$, $a_3$, …, $a_n$. It’s possible to teleport from point $x$ to point $y$ if there are teleporters in both of those points, and it costs $(x-y{)}^2$ energy.

You want to install some additional teleporters so that it is possible to get from the point $0$ to the point $a_n$ (possibly through some other teleporters) spending no more than $m$ energy in total. Each teleporter you install must be located in an integer point.

What is the minimum number of teleporters you have to install?

Input

The first line contains one integer $n$ ($1\le n\le 2\cdot 10^5$).

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_1<a_2<a_3<\cdots <a_n\le 10^9$).

The third line contains one integer $m$ ($a_n\le m\le 10^{18}$).

Output

Print one integer — the minimum number of teleporters you have to install so that it is possible to get from $0$ to $a_n$ spending at most $m$ energy. It can be shown that it’s always possible under the constraints from the input format.

Examples

Input

Copy

2
1 5
7

Output

Copy

2

Input

Copy

2
1 5
6

Output

Copy

3

Input

Copy

1
5
5

Output

Copy

4

Input

Copy

1
1000000000
1000000043

Output

Copy

999999978

好的，下面是问题的中文解答。

问题分析：

我们需要解决一个类似于“给定一个数组，如何通过贪心策略和二分法优化选择分段策略”的问题。通过右到左的贪心策略，能够清晰地确定每个位置的最优决策。我们需要对数组 b 进行操作，逐步减少它的元素，并在此过程中管理一系列的变量来控制进度和代价。我们将使用如下的关键变量：

关键变量：

• sum：表示当前已有的进度所需从当前元素中扣除的总量。
• cnt：表示当前活动的进度数量。
• closed：一个长度为 n 的数组，其中 closed[i] 表示在位置 i+1 结束的进度数量。
• b：表示每段区间的距离（或能量），我们会根据当前进度动态调整它。

解决思路：

1. 从右到左的贪心处理：
   我们从右往左处理数组 b，这样可以确保在每个步骤中清楚知道当前进度的影响，避免因未来的选择影响当前决策。每个位置 i 的值 b[i] 需要被当前的进度影响，并决定是否需要添加新的进度。

2. 更新进度：
   当我们考虑到元素 b[i] 时，首先会根据当前的 sum （减去当前进度的总量）来更新 b[i]。如果 b[i] 大于 0，则我们需要增加新的进度。每个新进度的大小是 el = min(k, i + 1)，表示每个进度所能影响的最大范围。

   然后，我们计算需要多少个进度来满足 b[i]，公式如下：
   $\text{need}=\lceil \frac{b[i]}{el}\rceil$
   其中，el 是每个进度能处理的最大距离（即 min(k, i + 1)）。

3. 更新进度状态：

   • 每次我们添加 need 个新的进度，就更新总进度 sum，将 sum 增加 el * need。
   • 更新 cnt，增加 need。
   • 同时，更新 closed 数组，表示哪些进度会在当前索引之前结束。

4. 时间复杂度：
   由于我们是从右到左处理数组并且每步仅执行常数时间操作，因此时间复杂度为 O(n)，这是非常高效的。

二分法优化：

在这个问题中，我们需要合理地管理每个区间的传送器数量。假设我们可以将每个区间的长度为 len，放置 x 个传送器，计算所需的代价。该代价计算公式为：

$f(len,x)=(x-(len\mathrm{mod}(x+1)))\times {\left(\lfloor \frac{len+1}{x+1}\rfloor \right)}^2+(len\mathrm{mod}(x+1))\times {\left(\lceil \frac{len+1}{x+1}\rceil \right)}^2$

通过这个公式，我们可以看出，随着传送器数量 x 的增加，每段的代价减少的幅度是单调不增的。因此，我们可以使用二分法来优化我们所需要的最小代价。

算法步骤：

1. 二分法搜索： 我们通过二分法搜索传送器数量 x，以最小化每段的代价，并确保总代价不超过给定的最大值 m。

2. 计算总代价： 在每次二分搜索过程中，我们计算相应的总代价，并更新最优解。

3. 贪心策略： 一旦确定了每段最优的传送器数量，我们就可以按贪心策略将传送器分配到各个区间，确保总代价最小。

关键的数学公式

1. 对于一段距离 len，如果我们需要安装 x 个传送门，则每段之间的平均距离为 len / (x + 1)，我们可以通过这个公式来计算每段所需的额外能量。

2. 对于每段距离的能量消耗计算，使用 f(len, x) 来表示在该段上安装 x 个传送门的总代价，可以通过分段函数来计算。

代码分析

#include <map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;const int inf = 1e9 + 7;
const int N = 2e5 + 10;
int n;
int a[N];
int d[N];
int ans, m;
int cnt, cost;int dodo(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;
}int check(int x)
{cnt = 0, cost = 0;for (int i = 1; i <= n; ++i){int l = 1, r = d[i];int ans = 1;while (l <= r){int mid = (l + r) / 2;if (dodo(mid, d[i]) - dodo(mid + 1, d[i]) >= x){ans = mid + 1;l = mid + 1;}else{r = mid - 1;}}cnt += ans - 1;cost += dodo(ans, d[i]);}return cost <= m;
}void solved()
{cin >> n;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) / 2;if (check(mid)){l = mid + 1;save = mid;}else{r = mid - 1;}}check(save);cnt -= (m - cost) / save;cout << cnt;
}signed main()
{BoBoowen;int T = 1;while (T--){solved();}
}

代码解释

1. dodo 函数：计算在一个区间内安装一定数量传送门的代价。这个函数帮助我们计算每个区间内根据给定的传送门数量需要的能量。

2. check 函数：检查在给定的 x 值下，是否能在总消耗能量不超过 m 的情况下，满足从 0 到 a_n 的路径。使用二分查找来优化传送门的安装。

3. 主函数 solved：初始化数据并调用二分查找来找到最小的 x，并根据该 x 值计算出最小的传送门数量。

时间复杂度

1. dodo 函数：每次计算需要 O(1) 时间。
2. check 函数：对每个区间进行二分查找，时间复杂度为 O(n log n)。
3. 总体时间复杂度：O(n log n)，适合题目中最大的输入规模。

总结

这个问题是一个典型的优化问题，可以使用贪心策略和二分查找结合来解决。通过区间分割和计算每段距离所需的传送门数量，最终得到最优解。