AcWing 789. 数的范围
原题链接
简单
作者:
怎么不下雨
,
2025-04-03 17:19:36
· 广东
,
所有人可见
,
阅读 2
这才是最好的模板!
int l = 0, r = a.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] >= k) r = mid - 1;
else l = mid + 1;
}
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] <= k) l = mid + 1;
else r = mid - 1;
}
代码
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#define ios_sync ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 100010;
vector<int> a;
int main() {
ios_sync;
int n, q;
cin >> n >> q;
for (int i = 0; i < n; i ++) {
int x;
cin >> x;
a.push_back(x);
}
sort(a.begin(), a.end());
for (int i = 0; i < q; i ++) {
int k;
cin >> k;
int l = 0, r = a.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] >= k) r = mid - 1;
else l = mid + 1;
}
int x;
if (a[l] != k) x = -1;
else x = l;
l = 0, r = a.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] <= k) l = mid + 1;
else r = mid - 1;
}
int y;
if (a[r] != k) y = -1;
else y = r;
cout << x << ' ' << y << '\n';
}
return 0;
}