解成电OJ1003真实的谎言的记要

解成电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

#include<stdio.h>    bool join(int *AB,int A,int B)  {       int a=AB[0],b=AB[1];         if(B<a||A>b)return false;        if(B<b)b=B;       if(A>a)a=A;       if(AB[2]+1>b)return false;                     AB[0]=a;       AB[1]=b;       AB[2]++;                     return true;    }  int main()  {      int T;      scanf("%d",&T);            int AB[3],N,A,B,maxcount;      int i,j;      for(i=0;i<T;i++)      {             AB[0]=AB[1]=0;          AB[2]=-1;                   scanf("%d",&N);                    maxcount=0;           for(j=0;j<N;j++)          {            scanf("%d%d",&A,&B);                        if(B<1||A>N)continue;            if(AB[2]==-1)            {               AB[0]=A;AB[1]=B;               AB[2]=1;               continue;            }             if(join(AB,A,B))continue;            if(AB[2]>=AB[0])                if(AB[2]>maxcount)                    maxcount=AB[2];            AB[0]=A;AB[1]=B;            AB[2]=1;          }            if(AB[2]>=AB[0])                if(AB[2]>maxcount)                    maxcount=AB[2];          if(maxcount>0)printf("%d\n",maxcount);          else printf("-1\n");      }      return 0;  }

查看更多 下一篇