CF1730A/B题解
|
题解
|
阅读次
|
676 字
|
2 分钟

TJ 时间

A 题：

太水了，解法各种各样，真的没必要将（真的！

看看隔壁的TJ吧（真的没必要讲，纯模拟。

关于隔壁为啥还没有 B 题TJ（DDDD

B 题：

题意：

坐标轴 n 个点，每个点的坐标是 xi (凑合着看吧，我还不会ktext），然而每个点都有一个前提时间 ti，我们需要寻找一个点 x0，使得 所有的 |xi - x0| + ti 中最大的最小。（千万不要理解成加起来最小啊，我就是掉了这个坑！

那天晚上，想了大约有 15-25 分钟，终于想出这么二分了（题目标签就是二分

智慧之神 said：二分出一个点。

我不知道可不可行，但我对此毫无想法（大几率是不可行的

应该是二分时间。

思路：Link

看不懂对吧，但是伟大的 czx 却看懂了。

详细讲一下吧QAQ

我们二分的是时间啊，和一些二分题目不同，大部分二分查找题目都是直接二分答案的。

那么对于第 i 个点

zzb

那么距离 xi 长为 mid - ti(mid > ti) 的距离之内的范围所有的点是不是都可以作为 x0 啊（只考虑只有这一点的情况）。

zzb

然鹅，有多个点呢？

很明显，就是区间重叠部分，所以我们来个递归，枚举每一个点，找到重叠部分。

这时，我们就会收到来自 czx 的嘲讽

1
@Acerkaio 你学过解不等式组吗？@Acerkaio 你学过解不等式组吗？@Acerkaio 你学过解不等式组吗？@Acerkaio 你学过解不等式组吗？@Acerkaio 你学过解不等式组吗？@Acerkaio 你学过解不等式组吗？@Acerkaio 你学过解不等式组吗？@Acerkaio 你学过解不等式组吗？

然后就会收到来自 czx 的温馨提示：左端点全部取max，右端点全部取min，最后 L<=R 即为有解

CODE：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100001], t[100001];
int al, ar, n;
inline bool check(int time) {
	al = -1, ar = 1e9;
	for (int i = 1; i <= n; i++) {
		if (time - t[i] < 0)
			return false;
		al = max(al, a[i] - (time - t[i]));
		ar = min(ar, a[i] + (time - t[i]));
	}
	return al <= ar;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
    	cin >> n;
    	for (int i = 1; i <= n; i++) cin >> a[i];
    	for (int i = 1; i <= n; i++) cin >> t[i];
    	double l = 0, r = 1e9;
    	double ans;
    	while (l <= r && r - l > 0.0000001) {
    		double mid = (l + r) / 2.0;
    		if (check(mid)) {
    			ans = (al + ar) / 2.0;
    			r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		printf("%.6lf\n", ans);
	}
    return 0;
}

Special Thanks: CZX

上一篇
下一篇