自动搬运

查看原文

来自洛谷，原作者为

	Adove 私者一时，公者千古

搬运于2025-08-24 21:58:28，当前版本为作者最后更新于2018-11-07 12:17:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题我们维护一个大于等于某值的前缀和和一个小于等于某值的后缀和

从左往右扫，对每个位置保证最少贡献的情况下取最小的那个

时间复杂度$\Theta(NK)$

说实话这题紫题难度有点偏高，差不多是提高组级别难度

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
using namespace std;

const int MAXN=1e5+5;
const int MAXM=105;

int n,m;
int a[MAXN];
int lis[2][MAXM];
long long ans;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){scanf("%d",&a[i]);if(a[i]!=-1) ++lis[1][a[i]];}
	for(int i=1;i<=m;++i) lis[1][i]+=lis[1][i-1];
	for(int i=1;i<=n;++i){
		if(a[i]==-1){
			int c=0,d=0,ct=0,mx=0x7fffffff;
			for(int j=1;j<=m;++j){
				if(lis[0][j+1]+lis[1][j-1]<mx) mx=lis[0][j+1]+lis[1][j-1],ct=j;
			}a[i]=ct;
		}else for(int j=a[i];j<=m;++j) --lis[1][j];
		ans+=lis[0][a[i]+1];
		for(int j=1;j<=a[i];++j) ++lis[0][j];
	}printf("%lld\n",ans);
	return 0;
}