传送门：主题库/比赛里
题目大意
给你
n
n
n 个数，你可以选一个数让他插到原数组中的任意位置，经过多次操作后，使得每一个第
1
1
1 到
k
k
k 小的数都在
k
+
1
k+1
k+1 到
k
+
n
k+n
k+n 位置中，每一个第
k
+
1
k+1
k+1 到
k
×
2
k\times2
k×2 小的数都在
k
+
1
k+1
k+1 到
k
×
2
k\times2
k×2 位置中，
⋯
\cdots
⋯，每一个第
n
−
k
+
1
n-k+1
n−k+1 到
n
n
n 小的数在
n
−
k
+
1
n-k+1
n−k+1 到
n
n
n 位置中。求最小的操作次数
思路
因为这个操作是可以插入的，那么就不能直接用逆序对的方法来求。
很显然，这个操作数绝对不会超过
n
n
n，也就是每一个数最多只能被操作一次，不然就太浪费。
那么，为了让操作次数少，也就是不被操作的数多，就是这些不被操作的数一定满足——他们应该去的间隔（每
k
k
k 个位置算一个间隔）一定是不降的，不然就会出现左边的数应该在右边，右边的数应该在左边，就不行了。
所以，这就是一个最长上升子序列，用树状数组直接搞就可以了。
代码
#include<cstdio>
#include<algorithm>
using namespace std
;
int n
,k
;
struct zj
{
int num
,id
,rank
;
}a
[500001];
bool cmp1(const zj
&x
,const zj
&y
){
return x
.num
<y
.num
;
}
bool cmp2(const zj
&x
,const zj
&y
){
return x
.id
<y
.id
;
}
int f
[500001];
int c
[500001];
void add(int x
,int y
){
for(int i
=x
;i
<=n
/k
;i
+=(i
&-i
)){
if(c
[i
]<y
)c
[i
]=y
;
}
}
int get(int x
){
int maxx
=0;
for(int i
=x
;i
;i
-=(i
&-i
)){
if(c
[i
]>maxx
)maxx
=c
[i
];
}
return maxx
;
}
int main(){
scanf("%d%d",&n
,&k
);
for(int i
=1;i
<=n
;i
++)scanf("%d",&a
[i
].num
),a
[i
].id
=i
;
sort(a
+1,a
+1+n
,cmp1
);
for(int i
=1;i
<=n
;i
++)a
[i
].rank
=(i
-1)/k
+1;
sort(a
+1,a
+1+n
,cmp2
);
int maxx
=0;
for(int i
=1;i
<=n
;i
++){
f
[i
]=get(a
[i
].rank
)+1;
add(a
[i
].rank
,f
[i
]);
if(maxx
<f
[i
])maxx
=f
[i
];
}
printf("%d",n
-maxx
);
return 0;
}
