郑州好的网站设计公司,网站建设公司保定市,哪个网站衬衣做的好,店面设计效果图大全【洛谷】P10417 [蓝桥杯 2023 国 A] 第 K 小的和 的题解
题目传送门
题解
CSP-S1 补全程序#xff0c;致敬全 A 的答案#xff0c;和神奇的预言家。
写一下这篇的题解说不定能加 CSP 2024 的 RP 首先看到 k k k 这么大的一个常数#xff0c;就想到了二分。然后写一个判…【洛谷】P10417 [蓝桥杯 2023 国 A] 第 K 小的和 的题解
题目传送门
题解
CSP-S1 补全程序致敬全 A 的答案和神奇的预言家。
写一下这篇的题解说不定能加 CSP 2024 的 RP 首先看到 k k k 这么大的一个常数就想到了二分。然后写一个判断的函数枚举 A A A 序列里面的数然后再找 B B B 序列能和 A A A 序列里选出来的数加起来之和小于等于 t t t 即可。
但是这样的话可能会超时所以我们把 B B B 序列的循环改成二分注意要二分必须在有序的情况下所以提前排序。时间复杂度 O ( n log m ) O(n \log m) O(nlogm)
不开 long long 见祖宗
代码
#include bits/stdc.h
#define lowbit(x) x (-x)
#define endl \n
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
namespace fastIO {inline int read() {register int x 0, f 1;register char c getchar();while (c 0 || c 9) {if(c -) f -1;c getchar();}while (c 0 c 9) x x * 10 c - 0, c getchar();return x * f;}inline void write(int x) {if(x 0) putchar(-), x -x;if(x 9) write(x / 10);putchar(x % 10 0);return;}
}
using namespace fastIO;
int n, m, k, a[100005], b[100005];
bool check (int x) {int res 0;for (int i 1; i n; i) {res upper_bound (b 1, b m 1, x - a[i]) - b - 1;}return res k;
}
signed main() {//freopen(.in,r,stdin);//freopen(.out,w,stdout);n read(), m read(), k read();for(int i 1; i n; i ) {a[i] read();}for(int i 1; i m; i ) {b[i] read();}sort(b 1, b m 1);int l 0, r INT_MAX;while (l r) {int mid (l r) 1;if (check (mid)) {r mid;}else l mid 1;}write(l);return 0;
}
