[置顶] 解成电OJ1003真实的谎言的记录

原题目
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

分析
        题目什么意思呢?
        总共N个人,那说真话最多只有N个人,为什么ai和bi的值可以远大于N呢?结合示例不难得知,原来ai和bi的值只是给个说真话的人数的范围,说真话的人数自然是在N以内的。假如某人可能说真话,则其给出的区间必然包含1至N的某值,因此说出区间[0,0]的那家伙肯定说假话;如果给出的区间左端值ai>N,那么他也肯定说假话。因此,判断可能说真话的最多人数时,可以不考虑这些必然说假话的人。假如最多X个人全部说真话(当然其余N-X说假话了),那么X必然在他们给出的交集区间[ax,bx]中。
      于是,本题的意思就是寻找最大的X满足:X属于[ax,bx],其中[ax,bx]表示X个人给出的交集区间。
         那如何才能得到呢?对任意一个给出的区间[ai,bi],他能结合的可能其他人数是有限的,不妨设为Xi,Xi的最大值取决于区间的右端值。N个人中,可能有些部分之间没有交集,应该单独考虑这些部分,最后再比较。对于有交集的部分,可以证明只有按照Xi有序进行结合,才能得到最大的X。结合所能给出的可能全部说真话的人数取决于他们当中最小的Xi,不妨设X1<X2<X3(逆序等效),则X1和X2结合、X1和X3结合均取决于X1。如果X1、X2、X3能全部结合,即X1+X2+X3在他们的交集区间中,那么与顺序无关,但是倘若只有部分能结合,则显然能结合的部分的最小Xi同较小Xk结合,使得剩下的Xj较大,则可能使Xj同其他结合得到更大值。因此,可以按照给出区间的右端值进行排序,然后再逐个结合判断。
        判断的大致过程:若有交集并且结合后的X值不大于交集右端值(可能也小于左端值,因为结合尚未完成),则结合;否则表示这部分结合完毕,可以判断是否可能是符合题意的X,即X是否在交集区间中,若是则记录以便同其他部分比较,否则继续另一部分的结合。最后比较各部分得到最大的X值即为所求。

解答
        我提交了好几次,推测出成电OJ的测试数据已经是排好序的了,因此解题代码中就不考虑排序了。实际上,我写了排序后,测了几组数据没问题,而AC的代码(即未排序的)测未排序的数据会出错。提交排序的后,结果run time error,原来不允许调用qsort快排例程。

附录
       下面是我的AC代码。这个代码的时间39ms、空间852KB,在该题Best Solution中排第九,而且所占空间是最小的。但是代码长度略长,后来去掉join函数简化到约50行,可是结果却没这个好。最后本人能力实在有限,不对之处恳请指正,不胜感激。

真实的谎言 (1003 )

User: xuebao2013 Result: AcceptedDate: 2013-10-10 03:07:55

  1. #include<stdio.h>
  2. bool join(int *AB,int A,int B)
  3. {
  4. int a=AB[0],b=AB[1];
  5. if(B<a||A>b)return false;
  6. if(B<b)b=B;
  7. if(A>a)a=A;
  8. if(AB[2]+1>b)return false;
  9. AB[0]=a;
  10. AB[1]=b;
  11. AB[2]++;
  12. return true;
  13. }
  14. int main()
  15. {
  16. int T;
  17. scanf("%d",&T);
  18. int AB[3],N,A,B,maxcount;
  19. int i,j;
  20. for(i=0;i<T;i++)
  21. {
  22. AB[0]=AB[1]=0;
  23. AB[2]=-1;
  24. scanf("%d",&N);
  25. maxcount=0;
  26. for(j=0;j<N;j++)
  27. {
  28. scanf("%d%d",&A,&B);
  29. if(B<1||A>N)continue;
  30. if(AB[2]==-1)
  31. {
  32. AB[0]=A;AB[1]=B;
  33. AB[2]=1;
  34. continue;
  35. }
  36. if(join(AB,A,B))continue;
  37. if(AB[2]>=AB[0])
  38. if(AB[2]>maxcount)
  39. maxcount=AB[2];
  40. AB[0]=A;AB[1]=B;
  41. AB[2]=1;
  42. }
  43. if(AB[2]>=AB[0])
  44. if(AB[2]>maxcount)
  45. maxcount=AB[2];
  46. if(maxcount>0)printf("%d\n",maxcount);
  47. else printf("-1\n");
  48. }
  49. return 0;
  50. }
上一篇:Pyhton爬虫实战 - 抓取BOSS直聘职位描述 和 数据清洗


下一篇:自己封装一个Log模块