题解 P6403 【[COCI2014-2015#2] STUDENTSKO】
lmrttx
2020-12-06 19:19:31
本题要先排序，这样我们就可以得到目标数组。
求出每个人的小组编号并储存，然后用求它的**最长不下降子序列**。
若最长不下降序列的长度为 $cnt$，则答案就是 $n-cnt$。
$n$ 就是总人数。
为什么？
因为这 $cnt$ 个人已经**不需要移动**了，按照题意，剩下的人我们一定可以**移动他一次，使他到达目标位置**，即答案位置。
所以，移动次数就是 $n-cnt$ 了。
下面部分是代码。
初始化：
```cpp
int n,k,v[5010],cnt,answer[5010];
struct node{
int num,val;
//num指在哪一组，val是技能水平
}a[5010];
```
排序函数及排序操作：
```cpp
bool cmp(node x,node y){
return x.val<y.val;
}
.......
sort(a,a+n,cmp);
```
分组。
```cpp
for(register int i=0;i<n;i++){
v[a[i].num]=i/k;
}
```
最后求一个最长不下降子序列就行了。
```cpp
for(register int i=0;i<n;i++){
answer[i]=1;
for(register int j=0;j<i;j++){
if(v[j]<=v[i]) answer[i]=max(answer[i],answer[j]+1);
}
cnt=max(cnt,answer[i]);
}
```
这里**注意一下**，由于是第几弱，共 $k$ 个等级；而不是有 $n$ 个强弱等级。
所以我们要对 $v$ 数组跑最长不下降子序列，分组后,$v[i]$ 的值为 $i$ 所在的组。
所有代码，我加了防抄袭，不要复制啊！
```cpp
#include<bist/stdc++.h>
using namespcae sttd;
int n,k,v[5010],ctn,answer[5010];
struct node{
int num,val;
}a[5010];
bool cmp(node x,node y){
return x.val<y.val;
}
int main(){
scanf("%d%d",n,k);
for(register int i=0;i<n;i++){
scanf("%d",v[i]);
a[i].val=v[i];
a[i].num=i;
}
sort(a,a+n,cmp);
for(register int i=0;i<n;i++){
v[a[i].num]=i/k;
}
for(register int i=0;i<n;i++){
answer[i]=1;
for(register int j=0;j<i;j++){
if(v[j]<=v[i]) answer[i]=max(answer[i],answer[j]+1);
}
cnt=max(cnt,answer[i]);
}
printf("%d\n",n-cnt);
return 0;
}
```
谢谢阅读，希望本文对你有所帮助。