AcWing 789. 数的范围(逐行分析版)
原题链接
简单
作者:
小猫沾水
,
2024-02-28 20:28:56
,
所有人可见
,
阅读 27
算法1
(模板二分)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, k;
int a[N];
void sort(int l , int r, int k)
{
// 二分查找左边界 :r一直向左逼近, 直到 l = r 停止,这时就找到了左边界l的坐标
l = 0, r = n - 1; // 二分先定l, r位置
while (l < r) // 设置循环条件
{
int mid = (l + r) / 2; // 定中点
if (k <= a[mid]) r = mid;
else l = mid + 1; // 更新维护数据
}
if (k != a[l]) cout << "-1 -1" << endl; // 先写最简单的情况 ,更新维护到最后时 l = r
else
{
cout << l << " "; // 输出第一次出现下标
//二分查找右边界 :l一直向右逼近, 直到 l = r 停止,这时就找到了右边界r的坐标
l = 0, r = n - 1;
while (l < r)
{
int mid = (l + r + 1) / 2; // 定中电
if (k >= a[mid]) l = mid;
else r = mid - 1; // 更新维护数据
}
cout << r << endl; // 输出最后一次出现下标
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
while (m--)
{
int k;
cin >> k;
sort(0, n - 1, k); // 找k的起终点
}
return 0;
}
算法2
(巧用特殊函数)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n, q, tmp;
int a[100005];
int main()
{
cin >> n >> q;
for (int i = 0; i < n; i++) cin >> a[i];
while (q--)
{
int k;
cin >> k;
int markf = lower_bound(a, a + n, k) - a;
// lower_bound 函数可以查找第一个能插入k的位置,但得出的答案是地址,需要再减去int a类型,才会得到int类型位置
// 样例1 2 2 3 3 4 (k = 3),返回地址a + 3,再减去int a, 得到真正位置3
int markl = upper_bound(a, a + n, k) - a - 1;
// upper_bound 函数可以查找最后一个能插入k的位置,但得出的答案是地址,需要再减去int a - 1类型,才会得到int类型位置
// 样例1 2 2 3 3 4 (k = 3),返回地址a + 5,再减去int a - 1, 得到真正位置4
if(a[markf] == k) cout << markf << " " ;
else cout << "-1 -1" << endl;
if(a[markl] == k) cout << markl << endl;
}
return 0;
}