题目:样例:
|
1 -1 0 -1 0 3 4 |
思路:
这道题也是个思维题,关键在于这种问题是有多个答案的,所以我们输出其中一种答案即可,也可能无法确定的,就要输出 -1。
题目意思是,给出 n 个人,n 个人说有 aj 个人撒谎,问可以确定的可能撒谎人数是多少,如果无法确定,输出 -1。
我们假设共有 n 种情况,分别可能有 i (0 <= i <= n) 个人撒谎,然后判断哪一个可以确定是真话了的,输出该答案即可。
而重要的是 判断哪一个可以确定是真话的条件是,当前这个人表示的说谎人数和我们假设 i 个人说谎人数的比较,即当 a[j] <= i 的时候,这个人有可能是真话。文章来源:https://www.uudwc.com/A/8dn8y/
文章来源地址https://www.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;
}