A. Trust Nobody

题目：样例：

7
2
1 2
2
2 2
2
0 0
1
1
1
0
5
5 5 3 3 5
6
5 3 6 6 3 5

思路：

        这道题也是个思维题，关键在于这种问题是有多个答案的，所以我们输出其中一种答案即可，也可能无法确定的，就要输出 -1。

        题目意思是，给出 n 个人，n 个人说有 aj 个人撒谎，问可以确定的可能撒谎人数是多少，如果无法确定，输出 -1。

        我们假设共有 n 种情况，分别可能有 i (0 <= i <= n) 个人撒谎，然后判断哪一个可以确定是真话了的，输出该答案即可。

        而重要的是 判断哪一个可以确定是真话的条件是，当前这个人表示的说谎人数和我们假设 i 个人说谎人数的比较，即当 a[j]  <= i 的时候，这个人有可能是真话。

文章来源地址https://uudwc.com/A/8dn8y

代码详解如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e5 + 10;

inline void solve()
{
	int a[N];	// 存储说话人 告诉我们的撒谎人数
	
	int n;	// n 个人
	cin >> n;
	
	for(int i = 0;i < n;++i)
	{
		// 存储说话人 说的撒谎人数
		cin >> a[i];
	}
	
	// 开始枚举情况,假设可能有 i 人说谎
	for(int i = 0;i <= n;++i)
	{
		int cnt = 0;	// 存储说真话的人数
		
		// 枚举每个人说话，比较是否符合我们的情况
		for(int j = 0;j < n;++j)
		{
			// 如果符合我们的情况，说真话人数累加
			// i >= a[j] 条件，表示 可能的 i 人说谎，而 j 号人说 有 a[j] 个人说慌，a[j] <= i
			// 即 a[j] 更接近答案一些，所以他有可能说的是真话的

			if(i >= a[j]) ++cnt;
		}
		
		// 如果说谎的人数等于了我们假设的情况
		// 那么输出该答案,有 i 个人说谎
		if(n - cnt == i)
		{
			cout << i << endl;
			return ;
		}
	}
	// 如果都不符合我们假设的情况，说明无法确定
	// 输出 -1
	cout << -1 << endl;
}


int main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：