題意 ：

• 紅石頭屬于紅隊，藍石頭屬于藍隊，分別給出所有紅色藍色石頭在數(shù)軸上的位置，構造目標點的位置（實數(shù)），使得紅隊勝利且獲得的分數(shù)盡可能多，紅隊的分數(shù) 等于 所有 比所有藍石頭離目標點近 的紅石頭 的數(shù)量，求 紅隊的最大分數(shù)或者如果無法贏就輸出impossivle

思路 ：

• 確定一個c點，紅隊中距離c的位置比藍隊中所有石頭都近的 石頭的個數(shù)，就是紅隊的分數(shù)，發(fā)現(xiàn)尋找c點不好找，于是轉(zhuǎn)換思路，發(fā)現(xiàn)兩個藍色石頭之間紅色石頭的數(shù)量的最大值即為答案，因為在兩個藍色石頭之間的紅色石頭一定比所有藍色石頭更近c，且藍色石頭外的紅色石頭不滿足比所有藍色石頭更近，因此，證為最優(yōu)解
• 先將兩個序列排序，然后用lower_bound或者upper_bound尋找在兩個藍色石頭間紅色石頭的個數(shù)
• 特別地，在第一個藍色石頭之前的和最后一個藍色石頭之后的也滿足條件，因此，在最前面和最后面再增加藍色石頭
• 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.南京）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。