TJ 时间
A 题:
太水了,解法各种各样,真的没必要将(真的!
看看隔壁的TJ吧(真的没必要讲,纯模拟。
关于隔壁为啥还没有 B 题TJ(DDDD
B 题:
题意:
坐标轴 n 个点,每个点的坐标是 xi (凑合着看吧,我还不会ktext),然而每个点都有一个前提时间 ti,我们需要寻找一个点 x0,使得 所有的 |xi - x0| + ti 中最大的最小。(千万不要理解成加起来最小啊,我就是掉了这个坑!
那天晚上,想了大约有 15-25 分钟,终于想出这么二分了(题目标签就是二分
智慧之神 said:二分出一个点。
我不知道可不可行,但我对此毫无想法(大几率是不可行的
应该是二分时间。
思路:Link
看不懂对吧,但是伟大的 czx 却看懂了。
详细讲一下吧QAQ
我们二分的是时间啊,和一些二分题目不同,大部分二分查找题目都是直接二分答案的。
那么对于第 i 个点
那么距离 xi 长为 mid - ti(mid > ti) 的距离之内的范围所有的点是不是都可以作为 x0 啊(只考虑只有这一点的情况)。
然鹅,有多个点呢?
很明显,就是区间重叠部分,所以我们来个递归,枚举每一个点,找到重叠部分。
这时,我们就会收到来自 czx 的嘲讽
1 | @Acerkaio 你学过解不等式组吗?@Acerkaio 你学过解不等式组吗?@Acerkaio 你学过解不等式组吗?@Acerkaio 你学过解不等式组吗?@Acerkaio 你学过解不等式组吗?@Acerkaio 你学过解不等式组吗?@Acerkaio 你学过解不等式组吗?@Acerkaio 你学过解不等式组吗? |
然后就会收到来自 czx 的温馨提示:左端点全部取max,右端点全部取min,最后 L<=R 即为有解
CODE:
1 |
|
Special Thanks: CZX