Let‘s Play Curling 二分，lower_bound（2020.12.南京）

题意 ：

• 红石头属于红队，蓝石头属于蓝队，分别给出所有红色蓝色石头在数轴上的位置，构造目标点的位置（实数），使得红队胜利且获得的分数尽可能多，红队的分数 等于 所有 比所有蓝石头离目标点近 的红石头 的数量，求 红队的最大分数或者如果无法赢就输出impossivle

思路 ：

• 确定一个c点，红队中距离c的位置比蓝队中所有石头都近的 石头的个数，就是红队的分数，发现寻找c点不好找，于是转换思路，发现两个蓝色石头之间红色石头的数量的最大值即为答案，因为在两个蓝色石头之间的红色石头一定比所有蓝色石头更近c，且蓝色石头外的红色石头不满足比所有蓝色石头更近，因此，证为最优解
• 先将两个序列排序，然后用lower_bound或者upper_bound寻找在两个蓝色石头间红色石头的个数
• 特别地，在第一个蓝色石头之前的和最后一个蓝色石头之后的也满足条件，因此，在最前面和最后面再增加蓝色石头
• lower_bound复杂度$O(logN)$，返回值是下标

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <unordered_set> #include <math.h> using namespace std;typedef long long ll; typedef pair<int, int> PII;#define endl '\n' #define fi first #define se second #define push_back #define rep(i, l, r) for (ll i = l; i <= r; i ++ )const int N = 1e5 + 10;int a[N], b[N];void solve() {int n, m; cin >> n >> m;for (int i = 1; i <= n && cin >> a[i]; i ++ );for (int i = 1; i <= m && cin >> b[i]; i ++ );sort(a + 1, a + n + 1);sort(b + 1, b + m + 1);b[0] = 0;b[m + 1] = 1000000001;int ans = 0;for (int i = 1; i <= m + 1; i ++ ){int l = b[i - 1], r = b[i];int len = lower_bound(a + 1, a + n + 1, r) - 1 - upper_bound(a + 1, a + n + 1, l) + 1;ans = max(ans, len);}if (ans == 0) cout << "Impossible" << endl;else cout << ans << endl; }int main() {cin.tie(nullptr) -> sync_with_stdio(false);int _;cin >> _;while (_ -- )solve();return 0; }

总结

以上是生活随笔为你收集整理的Let‘s Play Curling 二分，lower_bound（2020.12.南京）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。