题目描述

某班有 $n$ 个学生，编号 $1\sim n$。中午下课后，学生们陆续赶到食堂吃饭。食堂只有一个打饭窗口，所以学生们要排队打饭。

小猴是负责维护秩序的志愿者，他需要组织这些学生排成一条队伍买饭就餐。第 $i$ 位学生的耐心指数为 $a_i$​，它的含义是：如果在 $i$ 号之前，排队的人数超过了 $a_i$​，他就会放弃排队；否则他就会留下。

请问小猴应该如何安排这些学生的排队次序，才能使得留下吃饭的人最多？

【输入格式】

第一行一个整数 $n$；

第二行 $n$n 个整数 $a_1,a_2,\dots ,a_n$​。

【输出格式】

一行一个整数，表示留下吃饭的最大人数。

【输入输出样例#1】

输入#1

5
4 1 0 2 1

输出#1

4

【输入输出样例#2】

输入#2

7
2 2 6 5 4 0 6

输出#2

7

【输入输出样例#3】

输入#3

5
2 4 2 0 2

输出#3

4

【数据范围】

对于 $100\mathrm{\%}$ 的数据：$1\le n\le 10^6$，$0\le a_i\le n$。

【代码示例】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int n, p[MAXN];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}
	sort(p, p + n);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (p[i] >= ans) {
			ans++;
			//cout << p[i] << ' ' << ans << endl;
		}
	}
	cout << ans << endl;

}

【题目描述】

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\mathrm{.}\mathrm{.}\mathrm{.},a_n$​。

请你找到数组中只出现过一次的数当中最小的那个数。

输出找到的数的索引编号。

$a_1$​ 的索引编号为 $1$，$a_2$​ 的索引编号为 $2$，…，$a_n$ 的索引编号为 $n$。

【输入格式】

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\mathrm{.}\mathrm{.}\mathrm{.},a_n$​。

【输出格式】

每组数据输出一行结果，即满足条件的数的索引编号，如果不存在满足条件的数，则输出 $\text{−}1$。

【输入输出样例#1】

输入#1

2
2
1 1
3
2 1 3

输出#1

-1
2

【输入输出样例#2】

输入#2

4
4
2 2 2 3
1
1
5
2 3 2 4 2
6
1 1 5 5 4 4

输出#2

4
1
2
-1

【输入输出样例#3】

输入#3

3
2
2 1
6
5 5 4 3 1 1
7
1 2 3 4 3 2 1

输出#3

2
4
4

【数据范围】

$1\le T\le 2\times 10^4,$

$1\le n\le 2\times 10^5,$

$1\le a_i\le n,$

$\text{同一测试点内的所有}n\text{的和不超过}2\times 10^5$

【代码样例】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2 * 1e5 + 5;

struct m {
	int i;
	int num;
} a[MAXN];

bool cmp(m x, m y) {
	return x.i < y.i;
}

int main() {
	int t, n;
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i].i;
			a[i].num = i;
		}
		sort(a + 1, a + n + 1, cmp);
		int cnt = 1;
		m x = a[1];
		if (n == 1) {
			cout << 1 << endl;
		} else {
			for (int i = 2; i <= n; i++) {
				if (x.i == a[i].i) {
					cnt++;
					if (i == n) {
						cout << -1 << endl;
					}
				} else {
					if (cnt > 1) {
						x = a[i];
						cnt = 1;
						if (i == n) {
							cout << x.num << endl;
							break;
						}
					} else {
						cout << x.num << endl;
						break;
					}
				}
			}
		}

	}

}