社区讨论

WA on test 4求助

CF830AOffice Keys参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lo104nqi
此快照首次捕获于
2023/10/22 13:01
2 年前
此快照最后确认于
2023/11/02 12:31
2 年前
查看原帖
CPP
#include<iostream>
#include<algorithm>
#include<set>
#define int long long
using namespace std;
int a[114514], b[114514];
int n, k, p,mid;
bool key[114514];
bool cmp(int a, int b) { return abs(p-a) < abs(p-b); }
int find(int num) {
	int l = 1, r = k;
	while (l < r) {
		int m = (l + r) >> 1;
		if (p-(2 *b[m] - a[num]) <= mid||key[num])r = m;
		else l = m+1;
	}
	return l;
}
bool check() {
	for (int i = n; i >=1; i--) {
		int ky=find(a[i]);
		key[ky] = 1;
		if (abs(p - (2 * b[ky] - a[i]))>mid||ky==k) {
			return 0;
		}
	}
	return 1;
}
signed main() {
	
	cin >> n >> k >> p;
	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = 1; i <= k; i++)cin >> b[i];
	sort(a + 1, a + 1 + n,cmp);
	sort(b + 1, b + 1 + k,cmp);
	int l = 1, r = 1e18;
	while (l < r) {
		mid = (l + r) >> 1;
		memset(key, 0, sizeof(key));
		if (!check()) {
			l = mid + 1;
		}
		else r = mid;
	}
	cout << l;
}
/*
3 10 1500
106 160 129
1333 1532 1181 1091 1656 1698 1291 1741 1242 1163

*/
WA on test 4,贪心+二分,然后二分答案,代码应该没有问题,是思路错了吗

回复

0 条回复,欢迎继续交流。

正在加载回复...