K-Anonymous Sequence

给出一个递增的长度为n的序列\(\{a_i\}\),现在你可以进行一次操作，选择若干个数，分别减少任意一个正整数，定义权值为这些正整数之和，询问操作使得新序列的任意一个数都至少有k个数与之相同的最小权值，\(2 ≤ n ≤ 500000,2 ≤ k ≤ n,a_i\in[0,500000]\)。

解

就算题目没有告诉你序列是递增的，你也要想到排序，因为顺序对结果没有影响，从简单到困难的思想，我们对于第1个数而言，必然是相邻的数降到这个数，而且必须降到这个数，对于最终方案，必然也是降到几个旧序列中有的数（否则肯定不优），而且降的数都是相邻的，发现区间性，类似区间划分模型，设\(f[i][j]\)表示前j个数划分成i个区间的最小权值之和，(其中s为a的前缀和)我们有递推方程

\(f[i][j]=\min_{0\leq k<j}\{f[i-1][k]+\sum_{l=k+1}^j(a_l-a_{k+1})\}\)

其斜率优化式为

\(ja_{k+1}+f[i][j]-s_j=f[i-1][k]-s_k+ka_{k+1}\)

决策点集\((a_{k+1},f[i-1][k]-s_k+ka_{k+1})\)横坐标单调递增，斜率\(j\)单调递增，于是我们只要用单调队列维护下凸壳，让队首成为答案即可，时间复杂度显然\(O(n)\)。

参考代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#define il inline

#define ri register

#define Size 500050

#define ll long long

using namespace std;int T[Size],L,R;

ll dp[Size],sa[Size],y[Size],a[Size];

template<class free>il void read(free&);

int main(){int t,n,k;read(t);

	while(t--){

		memset(sa,0,sizeof(sa)),memset(a,0,sizeof(a)),read(n),read(k);

		for(int i(1);i<=n;++i)

			read(a[i]),sa[i]=sa[i-1]+a[i],dp[i]=1e11;L=R=1;

		for(int i(1);i<=k;++i)y[i]=dp[i]-sa[i]+i*a[i+1];

		for(int i(k);i<=n;++i){

			while(L<R&&i*(a[T[L+1]+1]-a[T[L]+1])>=(y[T[L+1]]-y[T[L]]))++L;

			dp[i]=dp[T[L]]+sa[i]-sa[T[L]]-(i-T[L])*a[T[L]+1],y[i]=dp[i]-sa[i]+i*a[i+1];

			while(L<R&&(y[T[R]]-y[T[R-1]])*(a[i-k+2]-a[T[R]+1])

				  >=(y[i-k+1]-y[T[R]])*(a[T[R]+1]-a[T[R-1]+1]))--R;T[++R]=i-k+1;

		}printf("%lld\n",dp[n]);

	}return 0;

}template<class free>

il void read(free &x){

	x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');

	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

}

巴特西

K-Anonymous Sequence

解

最新文章

热门文章