自动搬运

查看原文

来自洛谷，原作者为

	Acabbage 一颗卷心菜

搬运于2025-08-24 22:20:27，当前版本为作者最后更新于2023-11-17 21:58:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

发现没人用二分 + 贪心求最长不下降子序列的做法？那作为最优解的我就来发一篇吧。

题意简述

给定 $n$ 个数的序列 $a$，分为若干组，保证每组恰好 $k$ 个数。现要通过每次移动一个数的位置，使每组都满足其中所有数大于前一组并小于后一组，求移动次数的最小值。

解法

• 如何转化为最长不下降子序列问题？

显然，每个数应在的组是确定的，所以可以先对整个序列 $a$ 按数值大小 $v$ 来排序，再根据每个 $a_i$ 的原位置 $p$，用 $b$ 数组维护出其应在的组。

得到 $b$ 数组后，我们发现只有它的最长不下降子序列是不用转移位置的，所以只要求出 $b$ 的最长不下降子序列长度 $c$，移动次数的最小值即为 $n-c$。

• 如何用二分 + 贪心求最长不下降子序列？

维护一个单调栈 $s$，$s_c$ 表示长度为 $c$ 的最长不下降子序列末尾元素的最小值。对于每个 $b_i$，如果 $b_i\geq{s_i}$，满足单调不减性，直接入栈；否则，运用贪心思想在 $s$ 中二分查找第一个大于 $b_i$ 的位置 $t$，将 $s_t$ 替换为 $b_i$，即能最大限度地满足单调性。最后，$c$ 即为最长不下降子序列长度。

• 时间复杂度

$O(n\log{n})$

AC 代码（76ms）

#include<bits/stdc++.h>
#define ll long long
#define gch getchar() 
#define ub upper_bound
using namespace std;
ll rd()
{
	ll f=1,x=0; char c;
	while (!isdigit(c=gch)) if (c==45) f=-1;
	while (isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=gch;
	return f*x;
}
void wt(ll x)
{
	if (x<0) putchar('-'),x=-x;
	if (x>9) wt(x/10);
	putchar(x%10+'0');
}
const int N=5e3+5;
int n,k,t,c,b[N],s[N];
struct node
{
	int v,p;
	bool operator<(const node &x){return v<x.v;}
}a[N];
void in() //读入
{
	n=rd(),k=rd();
	for(int i=1;i<=n;i++)a[i].v=rd(),a[i].p=i;
}
void pre() //预处理
{
	sort(a+1,a+n+1); //排序
	for(int i=1;i<=n;i++)b[a[i].p]=(i-1)/k+1; //分组
}
void slv() //求最长不下降子序列
{
	s[++c]=b[1];
	for(int i=2;i<=n;i++)
	{
		if(b[i]>=s[c])s[++c]=b[i]; //满足单调性就直接入栈
		else t=ub(s+1,s+c+1,b[i])-s,s[t]=b[i]; //否则，用二分+贪心
	}
}
int main()
{
	in();pre();slv();wt(n-c); //答案是n-c
	return 0;
}