?

🏝?專欄：?【藍橋杯備篇】
🌅主頁：?f狐o貍x

"今日禿頭刷題，明日榮耀加冕！"

---

? ? ? ? 今天我們來練習二分算法

? ? ? ? 不熟悉二分算法的朋友可以看：【C語言刷怪篇】二分法_編程解決算術問題-CSDN博客

一、牛可樂和魔法封印

? ? ? ? 題目鏈接

????????牛可樂和魔法封印

? ? ? ? 題目描述

? ? ? ? 解題思路????????

? ? ? ? 這題就是讓我們找到左邊界，在找到右邊界，最后計算出在邊界里面的元素個數即可，尋找左右邊界的時候都可以用二分算法

? ? ? ? 解題代碼

#include <iostream>
using namespace std;typedef long long LL;const int N = 1e5 + 10;LL a[N];int n, q;int find(int x, int y)
{int left = 1, right = n;int rl = 0, rr = 0;// 尋找大于等于x的值while(left < right){int mid = (right + left) / 2;if(a[mid] >= x) right = mid;else left = mid + 1;}if(a[left] < x) return 0;rl = left;left = 1, right = n;// 尋找小于等與y的值      while(left < right){int mid = (right + left + 1) / 2;if(a[mid] <= y) left = mid;else right = mid - 1;}if(a[left] > y) return 0;rr = left;return rr - rl + 1;
}int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];cin >> q;while(q--){int x, y; cin >> x >> y;cout << find(x, y) << endl;}return 0;
}

二、P1102 A-B 數對

? ? ? ? 題目鏈接

????????P1102 A-B 數對

? ? ? ? 題目描述

? ? ? ? 解題思路

? ? ? ? 題目要求我們找到滿足A - B = C的個數，其實我們可以換一下，因為我們已知了A和C，也就是尋找B，即：A - C = B，因此我們只需要遍歷整個數組，找到每次符合條件的B的個數是多少就可以了

? ? ? ? 解題代碼

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 2e5 + 10;LL a[N];LL n, c;int main()
{cin >> n >> c;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);int ret = 0;for (int i = 1; i <= n; i++){LL b = a[i] - c;ret += upper_bound(a + 1, a + 1 + n, b) - lower_bound(a + 1, a + 1 + n, b);}cout << ret << endl;return 0;
}

三、P1678 煩惱的高考志愿

? ? ? ? 題目鏈接

????????P1678 煩惱的高考志愿

? ? ? ? 題目描述

? ? ? ? 解題思路

? ? ? ? 此題可以通過二分法找出大于等于學生成績的最小分數線，此時pos - 1的位置就是小于學生成績的最大分數線，兩個依次相減取小的即可

? ? ? ? 解題代碼

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 1e5 + 10;LL a[N];
int m, n;
LL b;int find(LL x)
{int left = 1, right = m;while (left < right){int mid = (left + right) / 2;if (a[mid] >= x) right = mid;else left = mid + 1;}return left;
}int main()
{cin >> m >> n;for (int i = 1; i <= m; i++) cin >> a[i];sort(a + 1, a + 1 + m);a[0] = 1e6 + 10;LL ret = 0;for (int i = 1; i <= n; i++){cin >> b;int pos = find(b);ret += min(abs(a[pos] - b), abs(a[pos - 1] - b));}cout << ret << endl;return 0;
}

? ? ? ? 今天的內容到這里就結束啦，明天我們繼續二分算法，886~