HDU 4768 二分的運用

題意:

      n個社團給同學發傳單,同學一共有1--2^31這麼多,每個社團有三個數A ,B ,C ,隻有

滿足 A ,A + C ,A + C + C ...A + KC <= B 的學生才能得到傳單,問你誰收到的傳單數是奇數,題目保證給的測試資料要麼沒有奇數的,要麼隻有一個是奇數個傳單.

思路:

     "題目保證給的測試資料要麼沒有奇數的,要麼隻有一個是奇數個傳單." ,這句非常關鍵,我們二分枚舉1--2^31,對于mid,算出0--mid一共發出去tmp張傳單,如果tmp是偶數那麼奇數的那個人一定不會在前面,因為隻有一個奇數,其他的都是偶數,奇數 + 偶數 = 奇數,偶數+ 偶數 = 偶數,是以可以根據目前的數是不是偶數就能斷定奇數的那個人在不在mid前面.對于不存在的這個判定,我是前直接跑出所有的個數,也就是求出範圍INF以前的所有,如果偶數那麼就不存在,否則就二分找,找到後在枚舉這個找到的人有多少個傳單,輸出來就行了.這個隻是用二分的特性去節省時間,和以往的二分不同,因為他不是在單調函數上查找的.

#include<stdio.h>

#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;
}