社区讨论

2024 CSPS 33题

11234567890regis
学术版参与者 7已保存回复 12

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@m1c6n7r7
此快照首次捕获于
2024/09/21 21:25
去年
此快照最后确认于
2025/11/05 00:12
4 个月前
查看原帖
我第 33 题做错了，于是看了几个讲解视频。
A 老师：这是显然的，选 A。 B 老师：这题选 A，下一题。
我：无语
为什么选 A 啊？我选的 B，我的逻辑如下：
先附源代码：
CPP
#include <iostream>
using namespace std;

const int maxn = 100005;

int n;
long long k;
int a[maxn], b[maxn];

int* upper_bound(int* a, int* an, int ai) {
	int l = 0, r = _______(33);
	while (l < r) {
		int mid = (l + r) >> 1;
		if (a[mid] > ai) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	return a + l;
}

long long get_rank(int sum)
{
	long long rank = 0;
	for (int i = 0; i < n; ++i) {
		rank += upper_bound(b, b + n, sum - a[i]) - b;
	}
	return rank;
}

int solve() {
	int l = 0, r = a[n - 1] + b[n - 1];
	while (l < r) {
		int mid = ((long long)l + r) >> 1;
		if (get_rank(mid) < k) {
			l = mid + 1;
		} else {
			r = mid;
		}
	}
	return l;
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; ++i) cin >> a[i];
	for (int i = 0; i < n; ++i) cin >> b[i];
	cout << solve() << endl;
}
(33):
A：an - a
B：an - a - 1
我的逻辑：
考虑 l = 0, 那么因为数组有 n 个元素，而如果 r = an - a 则 r - l + 1 = an - a - 0 + 1 = n + 1 个元素不对！
所以 r = an - a - 1 时 r - l + 1 = an - a - 1 - a - 0 + 1 = n 是对的，所以选 B。。。吗？
有巨佬帮我解释一下吗？

回复

共 12 条回复，欢迎继续交流。

正在加载回复...