真实的谎言(枚举)

本文主要是介绍真实的谎言(枚举)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

N个人做一个游戏,游戏中每个人说了一句话（可能是真的也可能是假的）
第i个人说：“N个人中有至少有ai个，至多有bi个人说的是真话！”(i = 1, 2, 3…..n)你能推断出最多能有多少个人说的是真话吗？
1 <= N <= 100000;
0 <= ai<=bi<=1000000000;

Input

第一行为一个整数T,代表测试数据的组数；
每组数据以n开头，接下来有n行，每行两个整数ai,bi（代表第i个人说的）;

Output

输出占一行。如果原问题有解，输出最多能有多少个人说的是真话；否则输出-1.

Sample Input

2
3
0 0
1 1
2 2
3
2 5
3 5
0 3

Sample Output

1
3

这道题....主要在逻辑判断...想明白了就很容易了

先用一个数组man 统计出所有人认为有i 个人说实话之和 最后判断man[i]如果大于i 则表示只有i 个人认为man[i]个人说实话如4个人认为5个人说实话..显然不能成立  在考虑man[i]如果小于i  也不可能  只有man[i]==i 才符合逻辑,由于是要最多要从n开始，具体见代码

#include <iostream>
#include <cstdio>
#include <cstring>
#define max 100006
using namespace std;
int man[max],i,j,a,b;
int main()
{int n,t;freopen("in.txt","r",stdin);scanf("%d",&t);while(t--){scanf("%d",&n);memset(man,0,sizeof(man));for(i=1;i<=n;i++){scanf("%d%d",&a,&b);for(j=a;j<=b&&j<=n;j++)    man[j]++;}for(i=n;i>0;i--)  if(man[i]==i) {printf("%d\n",i);break;}if(i==0)   printf("-1\n");}return 0;
}

题目来源 UESTC

这篇关于真实的谎言(枚举)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---