H-渴望力量吗 (二分查找应用)
程序员文章站
2022-06-02 11:58:56
...
时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld
题目描述
为了不断优化推荐效果,内涵段子(段友出征,寸草不生)每天要存储和处理海量数据。
假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为k。
因为一些特殊的原因,不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)
输入描述:
第1行为n代表用户的个数
第2行为n个整数,其中第i个数代表用户标号为i的用户对某类文章的喜好度
第3行为一个正整数q代表查询的组数
第4行到第(3+q)行,每行包含3个整数l,r,k代表一组查询,即标号为l<=i<=r的用户中对这类文章喜好值为k的用户的个数。
数据范围n <=
300000,q<=300000 ,k是整型
输出描述:
一共q行,每行一个整数代表喜好值为k的用户的个数
示例1
输入
5
1 2 3 3 5
3
1 2 1
2 4 5
3 5 3
输出
1
0
2
二分查找的思想,但是不怎么会用,然后看了题解,刚开始有点质疑,后来发现确实是这么回事哦。其实就是个稳定排序sort,然后lower_bound,upper_bound的联合使用,下面这张图比较好理解参考博客
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
typedef long long LL;
struct person
{
LL val;
int id;
bool operator<(const struct person &a)
{
if(val==a.val) return id<a.id;
return val<a.val;
}
}persons[maxn];
LL arr[maxn];
int ids[maxn];
int main()
{
int n,q,l,r;
LL k;;
while(scanf("%d",&n)==1)
{
for(int i=0;i<n;i++) scanf("%lld",&persons[i].val),persons[i].id=i+1;
sort(persons,persons+n);
for(int i=0;i<n;i++) arr[i]=persons[i].val,ids[i]=persons[i].id;
scanf("%d",&q);
while(q--)
{
scanf("%d%d%lld",&l,&r,&k);
int le=lower_bound(arr,arr+n,k)-arr,ri=upper_bound(arr,arr+n,k)-arr;
int L1=lower_bound(ids+le,ids+ri,l)-ids,R1=upper_bound(ids+le,ids+ri,r)-ids-1;
printf("%d\n",R1-L1+1);
}
}
return 0;
}
上一篇: 毕业旅行去哪好?十大毕业游景点推荐
下一篇: 梅州自驾游线路推荐
推荐阅读