Acw334.K匿名序列

题意：

给定一个长度为$n$的非严格递增整数序列，每次操作可以将其中的一个数减少一，问最少多少次操作后能够使得序列中的任何一个数在序列中都至少有$k-1$个数与之相同。

$n\leq 5e5,2\leq k\leq n$。

思路：

就相当于是把一个序列分成若干组，每组都有至少$k-1$个数字，花费就是这组的数字和$sum$，再减去最小值$min$乘以这个组的$cnt$，也就是$sum-(min*cnt)$。

贪心的考虑，假设说有三个数字$a_i,a_k,a_j,(i<k<j)$，那么从$a_j$转移到$a_i$的代价一定比从$a_k$到$a_i$的代价更大一些。

所以我们分成的组一定是连续的一段，那么就可以设计转移方程了。

设$f(i)$表示考虑前$i$个数的花费。
$$ f(i)=min\{f(j)+[sum(i)-sum(j)]-a(j+1)*(i-j)\} $$
其中$i-j\geq k$。

此时算法复杂度为$O(n^2)$，无法通过，考虑优化。

首先上式中的$sum(i)$和是一个定值，提取并把里头的式子分解出来。
$$ f(i)=sum(i)+min\{f(j)-sum(j)-(i-j)a(j+1)\} $$
考虑两个点$j,k(j<k)$。

当$k$优于$j$时，有：
$$ f(j)-sum(j)-(i-j)a(j+1)\geq f(k)-sum(k)-(i-k)a(k+1) $$
化简：
$$ \frac{f(j)-f(k)+sum(k)-sum(j)+ja(j+1)-ka(k+1)}{a(j+1)-a(k+1)}\leq i $$
这里要变号，因为$a(j+1)-a(k+1)$小于等于$0$。

这种斜率的形式可以用单调队列来维护。

设
$$ X(j,k)=\frac{f(j)-f(k)+sum(k)-sum(j)+ja(j+1)-ka(k+1)}{a(j+1)-a(k+1)} $$
队首维护应该很明白了，如果$X(j,k)\leq i$，就删除$j$，当然由于可能除数为0，所以我们用乘法来维护，所以又得变一次号，不要忘了。

队尾维护：求得是最小值，所以维护一个下凸壳。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5+10;
ll n, k;
ll a[maxn];
ll s[maxn];
ll f[maxn];
int q[maxn];

ll dy(int j, int k){
    return f[j]-f[k]-s[j]+s[k]+1ll*j*a[j+1]-1ll*k*a[k+1];
}

ll dx(int j, int k){
    return a[j+1]-a[k+1];
}

void solve()
{
    scanf("%lld%lld", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for(int i = 1; i <= n; i++) s[i] = s[i-1]+a[i];

    int hh = 1, tt = 1; q[1] = 0;
    for(int i = 1; i <= n; i++)
    {
        while(hh < tt && dy(q[hh], q[hh+1]) >= i*dx(q[hh], q[hh+1])) hh++;
        int j = q[hh];
        f[i] = f[j]+s[i]-s[j]-(i-j)*a[j+1];
        int z = i-(k-1);
        if(z >= k)
        {
            while(hh < tt)
            {
                int x = q[tt-1], y = q[tt];
                if(dy(x, y)*dx(y, z) >= dy(y, z)*dx(x, y)) tt--;
                else break;
            }
            q[++tt] = z;
        }
    }
    cout << f[n] << endl;
}

int main()
{
    int T; scanf("%d", &T);
    while(T--) solve();
    return 0;
}