题目

4、Unique Bid Auction–800
时间限制： | 空间限制：
题目描述：
有 个正整数 .
请找出 满足： 是独特的（即这 And does not exist in the number 相等的数）且 中所有小于 The numbers are not unique,
Or judge that there is no eligible condition .
有 组测试数据.
输入格式：
第一行仅有一个正整数 （ ）,表示测试数据的组数.
接下来有 组测试数据,每组共两行：
第一行仅一个正整数 （ ,and all test data 之和不超过 ）,表示有 个
数;
第二行有 个正整数 （ ）用空格隔开.
输出格式：
共 行,每行一个整数：If the set of test data does not meet the conditions ,输出 ;否则,输出符合条件的 .

思路

First use a bucket to store the number of occurrences of each number,Use another array to record whether all numbers smaller than a certain number are not unique.

代码实现

#include<bits/stdc++.h>
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;
}