Divide and conquer:Median(POJ 3579)-白红宇

Divide and conquer:Median(POJ 3579)

阅读量：5165 次

发布时间：2019-06-13

本文共 1214 字，大约阅读时间需要 4 分钟。

　　题目大意：给你一个很大的数组，要你求两个数之间的距离的中值

　　二分法常规题，一个pos位就搞定的事情

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 using namespace std; 6 typedef long long LL_INT; 7  8 static int nums[100002]; 9 bool judge(LL_INT, LL_INT,const int);10 11 int main(void)12 {13     int lb, rb, mid;14     LL_INT k, n;15 16     while (~scanf("%lld", &n))17     {18         k = n*(n - 1) / 2;19         k = k % 2 == 0 ? k / 2 : k / 2 + 1;20 21         for (int i = 0; i < n; i++)22             scanf("%d", &nums[i]);23         sort(nums, nums + n);24         lb = 0; rb = 1000000001;25         while (rb - lb > 1)26         {27             mid = (lb + rb) / 2;28             if (judge(k, n, mid)) lb = mid;29             else rb = mid;30         }31         printf("%d\n", rb);32     }33     return 0;34 }35 36 bool judge(LL_INT k, LL_INT n,const int x)37 {38     int i = 0, sum = 0, pos = 1;39     for (; i < n; i++)40     {41         for (; pos < n && nums[pos] - nums[i] <= x; pos++);42         sum += pos - i - 1;43         if (sum >= k) 44             return false;45     }46     return true;47 }