维什戴尔排序

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 13 总提交人数: 17
Special Judge

题目背景

维什戴尔排序由文化水平焚书坑儒的维什戴尔女士发明。

维什戴尔排序通过将一些项从数列中移除的方式来达到 $O(n)$ 的时间复杂度。

维什戴尔排序是这样进行的,首先,从数列的第二个项开始,如果它严格小于它的上一个项(忽略掉已经被移除的项之后),那么就将这个项删除,反之,保留它。不断向后遍历数列直到整个数列变成一个不下降的数列。比如说$[1,4,2,3,6,5,5,7,7]$维什戴尔排序后将会变成$[1,4,6,7,7]$

Xhesica 正在研究如何高效的利用维什戴尔排序。Xhesica 将满足以下条件的数列称为目光呆滞的:可以通过有限次对数列的任何一个子序列使用任意次维什戴尔排序(上一次维什戴尔排序的影响将会被保留)来把数列变成一个不上升的数列。

现在,Xhesica 将会给你一个长度为 $n$ 的 数组 $a$,请确定最小需要从中移除多少项来使这个数列变成目光呆滞的.

子序列是是从最初序列通过在开头或者结尾处去除某些元素但不破坏余下元素的相对位置(在前或在后)而形成的新序列。

输入格式

本题目具有多组测试数据。

第一行为一个正整数 $t$ $(1 \leq t \leq 5)$,为测试用例的组数。

每一组测试用例共两行,第一行一个数字 $n$ $(1 \leq n \leq 2000)$,为数列 $a$ 的大小。

第二行包括 $n$ 个数字,第 $i$ 个数字表示 $a_i$ $(1 \leq a_i \leq 10^9)$

输出格式

共 $t$ 行,每行一个正整数,表示最少需要移除多少项来达到目光呆滞

## 样例输入

6
7
3 6 4 9 2 5 2
5
5 4 4 2 2
8
2 2 4 4 6 6 10 10
1
1000
9
6 8 9 10 12 9 7 5 4
7
3 6 4 9 2 4 2

样例输出

2
0
6
0
4
2

样例解释

对于第一组测试数组,最优的答案是移除 $3$ 和 $9$ ,此时数列将变成 $[6,4,2,5,2]$,这个数列之所以是目光呆滞的,是因为我们可以首先对$[4,2,5]$使用维什戴尔排序来得到$[6,4,5,2]$,然后对 $[6,4,5]$使用维什戴尔排序来得到 $[6,2]$,显然这是不上升的。

对于第二组测试数据,显然不需要进行任何操作。

bug代码

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int t;
int n;
int a[200005];
int ans=1e9;
struct nod{
	int v;
	int p;
}nods[200005];
int cmp(const void *a,const void *b){
	struct nod x=*(struct nod*)a;
	struct nod y=*(struct nod*)b;
	return x.v!=y.v?x.v-y.v:x.p-y.p;
}
int main(){
	scanf("%d",&t);
	while(n--){
		scanf("%d",&n);
		ans=1e2;
		for(int i=1;i<=n;++i){
			a[i]=read();
			nods[i].p=i;
			nods[i].v=a[i];
		}
		qsort(nods,n+1,sizeof(nods),cmp);
		for(int i=1;i<=n;++i){
			if(nods[i].v!=nods[i-1].v)
				if(nods[i].p-1+i-1<ans)
					ans=nods[i].p-1+i-1;
		}
		printf("%d\n",ans);
	}
	return 0;
}

相关推荐