P6403 STUDENTSKO 题解

· · 题解

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

题意简述

给定 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;
}