首页 > 代码库 > 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 (二分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。