2020湖南大学ACM新生杯题解- D Treasure Cave
思路:
将地上的所有数和空中的数放在一起排序,空中的拿出意思就是可以最终从这个排好序的序列中抽出任意一个数,使得剩下的序列为严格的上升序列。
并且题目希望尽可能大,检查这个排好序的序列,如果这个序列中有两个连续相同的数就拿出其中一个,如果出现两组以上的相同的数,例如样例中的 3 4 1 4 4 排序后的序列为 1 4 4 4,有两组,就无法构成,
输出0,这个题差一丢丢就对了,可惜了。
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
int a[100005];
int main(void)
{
int t, n, x, pairs=0;
scanf("%d", &t);
for (int i = 0; i < t; ++i)
{
scanf("%d %d", &n, &x);
for (int j = 0; j < n; ++j)
{
scanf("%d", &a[j]);
}
a[n] = x;
std::sort(a, a + n + 1);
bool f = 1; // 可以逃出
int swap = 0; // 交换对象
pairs = 0;
for (int i = 1; i <= n; ++i)
{
if (a[i] == a[i-1]) pairs++, swap = a[i];
if (pairs > 1) { f = 0; break; }
}
if (f && pairs == 0) printf("%d\n", a[n]);
else if (f && pairs == 1) printf("%d\n", swap);
else printf("0\n");
}
return 0;
}