#include <iostream>
#include <vector>
#include <limits>
using namespace std;
using ll = long long;
// 我们使用 __int128 来防止可能的溢出
// 辅助函数：计算 x / y 的向下取整（y>0），注意 C++ 整数除法对负数是截断 toward 0
ll floorDiv(__int128 x, ll y) {
ll res = (long long)(x / y);
if ((x % y) != 0 && x < 0)
res -= 1;
return res;
}
struct Point {
int x; // 位置
ll y; // 对应值（这里用于 R[i] 或 T）
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
if (n == 0) return 0;
if (n == 1) {
cout << 0 << "\n" << a[0] << "\n";
return 0;
}
// 计算前缀和 A[i] = a[0] + ... + a[i]
vector<ll> A(n);
A[0] = a[0];
for (int i = 1; i < n; i++) {
A[i] = A[i - 1] + a[i];
}
ll S = A[n - 1];
// 求最优 b0 = X，使得对每个 i, (i+1)*X + i(i+1)/2 <= A[i]
// 即 X <= (A[i] - i(i+1)/2) / (i+1)
ll X = numeric_limits<ll>::max();
for (int i = 0; i < n; i++) {
ll candidate = floorDiv((__int128)(A[i] - (ll)i * (i + 1) / 2), (i + 1));
if (candidate < X) X = candidate;
}
// 构造基础等差序列 m[i] = X + i 及其前缀和 M[i]
vector<ll> m(n), M(n);
for (int i = 0; i < n; i++) {
m[i] = X + i;
}
M[0] = m[0];
for (int i = 1; i < n; i++) {
M[i] = M[i - 1] + m[i];
}
// 定义 R[i] = A[i] - M[i]
vector<ll> R(n);
for (int i = 0; i < n; i++) {
R[i] = A[i] - M[i];
}
// 总补充量 T = S - M[n-1]
ll T = S - M[n - 1];
// 下面求满足：
// D[0] = 0, D[n-1] = T, 且 D[i] <= R[i] (中间点不超过 R[i])
// 且 D 的差分非负且非递减（即 D 为离散凸函数）的最大 D。
// 根据理论，这个最大整数凸函数可通过“绑定点”确定：
// 定义点集 P0=(0,0), P_i=(i, R[i]) (1<=i<=n-2), P_{n-1}=(n-1, T)
// 然后取其下凸包，再在各区间内采用“均摊增量”的方式插值。
// 构造点集合
vector<Point> pts(n);
pts[0] = {0, 0};
for (int i = 1; i < n - 1; i++) {
pts[i] = {i, R[i]};
}
pts[n - 1] = {n - 1, T};
// 利用单调栈求下凸包（绑定点序列）
// 当新点使得前一段斜率不大时（即新的斜率更低或相等），就弹出前一点。
vector<int> hull;
for (int i = 0; i < n; i++) {
while (hull.size() >= 2) {
int j = hull[hull.size() - 2], k = hull[hull.size() - 1];
// 计算比较：若从 j 到 i 的斜率比从 j 到 k 的斜率更低或相等，则 k 可舍弃
__int128 left = (__int128)(pts[i].y - pts[j].y) * (k - j);
__int128 right = (__int128)(pts[k].y - pts[j].y) * (i - j);
if (left <= right) {
hull.pop_back();
} else {
break;
}
}
hull.push_back(i);
}
// 接下来在每个绑定点区间内均摊增量：
// 对于绑定点 p 到 q，设 L = q-p, 总增量 delta = pts[q].y - pts[p].y。
// 最大凸（整数）序列在该区间的增量分布为：令 a = delta / L, r = delta % L，
// 则第 k (0<=k<=L)个点的值为：
// D[p+k] = pts[p].y + (if k <= L-r then a*k, else a*(L-r) + (a+1)*(k - (L-r)) ).
vector<ll> D(n, 0);
// 遍历每个区间
for (size_t t = 0; t < hull.size() - 1; t++) {
int p = hull[t], q = hull[t + 1];
int L = q - p; // 区间个数（段数）
ll delta = pts[q].y - pts[p].y;
ll a_val = delta / L;
ll r_val = delta % L; // 余数，0 <= r_val < L
for (int k = 0; k <= L; k++) {
int i = p + k;
ll candidate;
if (k <= L - r_val) {
candidate = pts[p].y + a_val * k;
} else {
candidate = pts[p].y + a_val * (L - r_val) + (a_val + 1) * (k - (L - r_val));
}
// 为保险起见，确保中间点不超过 R[i]（但理论上已经满足）
if (i > 0 && i < n - 1 && candidate > R[i])
candidate = R[i];
if (i == 0) candidate = 0;
if (i == n - 1) candidate = T;
D[i] = candidate;
}
}
// 根据 D 求出 d (差分)，其中 d[0]=D[0], d[i] = D[i] - D[i-1] (i>=1)
vector<ll> d(n, 0);
d[0] = D[0];
for (int i = 1; i < n; i++) {
d[i] = D[i] - D[i - 1];
}
// 最后 b[i] = m[i] + d[i]
vector<ll> b(n);
for (int i = 0; i < n; i++) {
b[i] = m[i] + d[i];
}
// 计算最终前缀和 B[i] = sum_{j=0}^{i} b[j]，以及操作次数 ops = sum_{i=0}^{n-2} (A[i] - B[i])
vector<ll> B(n);
B[0] = b[0];
for (int i = 1; i < n; i++) {
B[i] = B[i - 1] + b[i];
}
ll ops = 0;
for (int i = 0; i < n - 1; i++) {
ops += (A[i] - B[i]);
}
cout << ops << "\n";
for (int i = 0; i < n; i++) {
cout << b[i] << (i + 1 == n ? "\n" : " ");
}
return 0;
}
下面给出一个总结，从数学思路到代码实现需要注意的关键点： --- ### 1. 数学模型与问题转化 - **问题描述** 给定数组 a，需要构造一个新序列 b，使得其前缀和满足一定约束（例如 b 的前缀和不超过 a 的前缀和），并且 b 具有“等差”基础（即 b[i] = b₀ + i）加上一个非负的、非递减的“修正项”。同时，还要求操作次数（前缀亏损的总和）最大。 - **分解问题** - **确定基准 b₀**：对任意 i，都有 (i+1)·b₀ + i(i+1)/2 ≤ A[i]，因此 b₀ 的上界是 \[ X = \min_{0\le i<n} \left\lfloor\frac{A[i]-\frac{i(i+1)}{2}}{i+1}\right\rfloor. \] 在代码中要特别注意对负数的除法，必须使用数学意义上的向下取整（floor）。 - **构造基准序列**：令 m[i] = X + i，计算其前缀和 M[i]，从而定义余量 \[ R[i] = A[i] - M[i], \] 这表示每个前缀还可额外补充多少。 - **构造最大凸函数 D** 目标是求一个离散凸函数 D，使得 - D[0] = 0, D[n-1] = T，其中 T = S – M[n-1]，S 为 a 的总和。 - 对任意 i，D[i] ≤ R[i]； - D 的差分 d[i] = D[i] - D[i-1] 非负且非递减。 证明可知：最大的满足这些条件的 D 序列正好对应于在点集合 \[ (0,0), (1,R[1]), \ldots, (n-2,R[n-2]), (n-1,T) \] 上的下凸包（凸包下插值）。 --- ### 2. 凸包构造与分段插值 - **构造下凸包** 使用单调栈对点进行扫描。每当加入一个新点时，比较新的斜率和之前两点的斜率，如果新的斜率更小或相等，就将前一个点舍弃。注意： - 斜率比较时避免浮点数运算，使用交叉乘法（乘积可能非常大时用 __int128）。 - **分段均摊插值** 对于每个凸包区间（绑定点 p 到 q），设： - 区间长度 L = q – p； - 总增量 delta = pts[q].y – pts[p].y。 为了使插值后的 D 在整数上最大且满足凸性，采用“均摊”方法： - 计算整数部分 a = delta / L 和余数 r = delta % L； - 对于区间内每个位置 k (0 ≤ k ≤ L)： - 如果 k ≤ L – r，则 D[p+k] = pts[p].y + a * k； - 否则 D[p+k] = pts[p].y + a * (L – r) + (a + 1) * (k - (L - r))。 这样分段插值既保证了整数值又能“均摊”总增量，确保 D 序列尽可能大且依然满足 D[i] ≤ R[i]。 --- ### 3. 代码实现注意点 - **精确的整数运算** - 使用自定义的 `floorDiv` 函数来实现数学意义上的向下取整，特别是处理负数除法时避免 C++ 默认的截断行为。 - 部分计算（如交叉乘法比较斜率）可能涉及大数运算，使用 `__int128` 避免溢出。 - **边界处理** - 计算 b₀ 时要遍历所有前缀，确保取到最小的合法值 X； - 插值时需要特别处理区间两端，保证 D[0]=0 与 D[n-1]=T。 - **凸包构造的细节** - 在构造下凸包时，使用“≤”判断可以避免在斜率相等时保留不必要的中间点，保证后续插值的正确性。 - **恢复最终序列** - 由 D 的差分得到 d 数组，最后 b[i] = m[i] + d[i]； - 根据 b 序列重建前缀和 B，并计算操作次数 ops。 --- ### 总结 1. **数学思路**： 将原问题转化为寻找满足约束的最大离散凸函数 D。利用凸包下插值得到最优 D，并通过均摊增量法在区间内精确插值。 2. **整数精度**： 避免浮点误差，所有计算（特别是涉及除法和斜率比较的部分）都使用整数运算，必要时使用 `__int128` 并自定义 floor 函数处理负数除法。 3. **代码细节**： - 正确计算 b₀ 的最优值 X； - 构造基础等差序列 m，并计算其前缀和； - 定义 R[i] 及 T，构造点集后利用单调栈构造下凸包； - 在每个绑定区间内用均摊法进行整数插值，确保 D 最大； - 恢复最终 b 序列，并计算操作次数。 这样，从数学建模到代码实现，每一步都精心处理了边界、取整和溢出问题，确保最终结果与预期完全一致。
京公网安备 11010502036488号