首页 > 代码库 > Gym 101064 D Black Hills golden jewels (二分)

Gym 101064 D Black Hills golden jewels (二分)

题目链接:http://codeforces.com/gym/101064/problem/D

问你两个数组合相加的第k大数是多少。

先sort数组,二分答案,然后判断其正确性(判断过程是枚举每个数然后二分)。

 1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 1e5 + 5;17 LL a[N], k, n;18 19 bool judge(LL val) {20     LL cnt = 0;21     for(int i = 1; i <= n; ++i) {22         LL pos = (LL)(upper_bound(a + 1, a + n + 1, val - a[i]) - a);23         if(pos > (LL)i)24             cnt += n - pos + 1;25         else26             cnt += n - pos;27     }28     cnt /= 2;29     return (n - 1)*n/2 - k >= cnt;30 }31 32 int main()33 {34     while(~scanf("%lld %lld", &n, &k)) {35         for(int i = 1; i <= n; ++i) {36             scanf("%lld", a + i);37         }38         sort(a + 1, a + n + 1);39         LL l = a[1] + a[2], r = a[n] + a[n - 1];40         while(l < r) {41             LL mid = (l + r) / 2;42             if(judge(mid)) {43                 r = mid;44             } else {45                 l = mid + 1;46             }47         }48         printf("%lld\n", l);49     }50     return 0;51 }

 

Gym 101064 D Black Hills golden jewels (二分)