题目

4、独特的投标拍卖–800
时间限制： | 空间限制：
题目描述：
有 个正整数 。
请找出 满足： 是独特的（即这 个数中不存在与 相等的数）且 中所有小于 的数都不是独特的，
或者判断出不存在符合条件的 。
有 组测试数据。
输入格式：
第一行仅有一个正整数 （ ），表示测试数据的组数。
接下来有 组测试数据，每组共两行：
第一行仅一个正整数 （ ，且所有测试数据的 之和不超过 ），表示有 个
数；
第二行有 个正整数 （ ）用空格隔开。
输出格式：
共 行，每行一个整数：若该组测试数据不存在符合条件的 ，输出 ；否则，输出符合条件的 。

思路

首先用一个桶去存储每个数出现的次数，用另一个数组去记录某一数所有比它小的数是否都不是独特的。

代码实现

#include
using namespace std;

const int maxn=2e5+10;
int t,n;
int a[maxn],cnt[maxn];
bool op[maxn];
int main(){
	scanf("%d",&t);
	while(t--){
		memset(cnt,0,sizeof(cnt));
		memset(op,false,sizeof(op));
		scanf("%d",&n);
		int ans=-1;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			cnt[a[i]]++;
		}
		op[1]=true;
		for(int i=2;i<=n;i++){
			if(cnt[i-1]>1||cnt[i-1]==0){
				if(op[i-1])op[i]=true;
			}
		}
		for(int i=1;i<=n;i++){
			if(cnt[a[i]]==1){
				if(op[a[i]]){
					ans=i;
					break;
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36