HDU 4768 二分的运用

"题目保证给的测试数据要么没有奇数的,要么只有一个是奇数个传单." ,这句非常关键,我们二分枚举1--2^31,对于mid,算出0--mid一共发出去tmp张传单,如果tmp是偶数那么奇数的那个人一定不会在前面,因为只有一个奇数,其他的都是偶数,奇数 + 偶数 = 奇数,偶数+ 偶数 = 偶数,所以可以根据当前的数是不是偶数就能断定奇数的那个人在不在mid前面.对于不存在的这个判定,我是前直接跑出所有的个数,也就是求出范围INF以前的所有,如果偶数那么就不存在,否则就二分找,找到后在枚举这个找到的人有多少个传单,输出来就行了.这个只是用二分的特性去节省时间,和以往的二分不同,因为他不是在单调函数上查找的.

#include
  
   

#define N 20000 + 100

    typedef struct { __int64 A
    ,B
    ,C
   ; }NODE
   ;

NODE node
   [N
   ]; __int64 minn
   (__int64 x
    ,__int64 y
   ) { return x
    < y
    ? x
    : y
   ; } __int64 solve
   (__int64 mid
    ,int n
   ) { __int64 sum
    = 0
   ; for(int i
    = 1
    ;i
    <= n
    ;i
    ++) { if(mid
    >= node
   [i
   ].A
   ) {
         sum
    += ((minn
   (mid
    ,node
   [i
   ].B
   ) - node
   [i
   ].A
   ) / node
   [i
   ].C
    + 1
   ); } } return sum
   ; } int main () { int n
    ,i
   ; __int64 INF
    = 1
   ; for(__int64 ii
    = 1
    ;ii
    <= 31
    ;ii
    ++)
   INF
    *= 2
   ; while(~scanf
   ("%d"
    ,&n
   )) { for(i
    = 1
    ;i
    <= n
    ;i
    ++)
      scanf
   ("%I64d %I64d %I64d"
    ,&node
   [i
   ].A
    ,&node
   [i
   ].B
    ,&node
   [i
   ].C
   ); __int64 tmp
    = solve
   (INF
    ,n
   ); if(tmp
    % 2
    == 0
   ) {
         puts
   ("DC Qiang is unhappy."
   ); continue; } __int64 low
    ,up
    ,mid
   ;
      low
    = 0
    ,up
    = INF
   ; while(up
    - low
    > 1
   ) {
         mid
    = (up
    + low
   ) / 2
   ;
         tmp
    = solve
   (mid
   , n
   ); if(tmp
    % 2
   )   up
    = mid
   ; else low
    = mid
   ; } __int64 ans_sum
    = 0
   ; for(i
    = 1
    ;i
    <= n
    ;i
    ++) { if(up
    <= node
   [i
   ].B
    && (up
    - node
   [i
   ].A
   ) % node
   [i
   ].C
    == 0
    && up
    >= node
   [i
   ].A
   )
         ans_sum
    ++; }
      printf
   ("%I64d %I64d\n"
    ,up
    ,ans_sum
   ); } return 0
   ; }