一、题目描述

原题链接

给一个长度为 $n$ 的系列 $a$，所有数均为非负整数，改变一个数的值所需要的代价为 $b[i]$，问使用最小的代价使得其变为等差数列。$1 \leq n \leq 2·10^{5},0 \leq a_i \leq 10^6$。

二、解题思路

  考虑数据的增长趋势，题目中全部为非负整数，若想组成等差数列，根据函数曲线可以得到其增长速度会很快，可以发现，若令方差为 $k$，那么当 $(i - 1)·k \ge 10^6$ 时，可以发现其后面的所有数若想形成等差数列，则对于后面每个元素都需要进行修改，顺着这个思路我们可以预估复杂度，考虑枚举每个方差 $k$，再枚举每个元素 $i$，在暴力情况下其复杂度为 $O(1e6*n)$，但因为有了上一个结论，则循环可以提前结束，即 $(i - 1)*k \leq 1e6$，化简后可以等效为 $k \leq \frac{1e6}{n}$，可以发现 $n$ 越大时，$k$ 所枚举的区间反而越小，其复杂度为一个调和级数，最终复杂度只有 $O(n·logn)$。

  考虑如何快速的判断一个数列变为公差 $k$ 的等差数列需要的最小代价，等差数列定义式为 $a_i = a_1 + (n-1)·k$，我们可以对于每一项减去后面的公差项，即 $i*k$（虽然和定义式相悖，但是可以看出谁和谁是一对的），此时若第 $i$ 个数和第 $j$ 个数的值相同，则为一个可组成的等差数列，可使用 $map$ 记录每类等差数列（即多个元素可以组成的等差数列）的总代价值，枚举记录 $ans = min(ans,sum - mp[x])$ 即可（$sum$ 为将所有元素进行修改的总代价，$x$ 为 $a_i - i*k$ 的值）。

三、AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1000010;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    vector<ll> a;
    vector<ll> b;
    int n;
    cin >> n;
    a.resize(n+1);
    b.resize(n+1);
    ll sum = 0;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
    }
    for(int i = 1;i<=n;i++){
        cin >> b[i];
        sum += b[i];
    }
    ll ans = LONG_LONG_MAX;
    for(int k = 0;k<=1e6;k++){
        unordered_map<ll,ll> mp;
        for(int i = 1;i <= n && (i - 1) * k <= 1e6;i++){
            a[i] -= i * k;
            mp[a[i]] += b[i];
            ans = min(ans,sum - mp[a[i]]);
            a[i] += i * k;
        }
    }
    cout << ans << endl;    
    system("pause");
    return 0;
}