题解 | #用户喜好#

二分查找(仅适用于排好序的序列)
lower_bound()函数
用于在指定区域内查找不小于(大于等于)目标值的第一个元素。语法规则如下

//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);

first 和 last 都为正向迭代器，[first, last) 用于指定函数的作用范围；val 用于指定目标元素；comp 用于自定义比较规则，此参数可以接收一个包含 2 个形参（第二个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。具体见以下链接的博文
http://c.biancheng.net/view/7521.html

upper_bound()函数
用于在指定范围内查找大于目标值的第一个元素。语法规则如下

//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);

具体见以下链接的博文
http://c.biancheng.net/view/7527.html

程序代码

#include<stdio.h>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);//用户数量
    vector<int> LikeValue(n);//记录用户喜好度的数组
    for(int i=0;i<n;i++)
    {
        scanf("%d",&LikeValue[i]);
    }
    int q;//查询组数
    scanf("%d",&q);
    vector<int> l(q),r(q),k(q);//查询限制
    for(int j=0;j<q;j++)
    {
        scanf("%d%d%d",&l[j],&r[j],&k[j]);
    }

    map<int, vector<int>> mp;//将用户喜好度和用户下标建立对应的map
    for(int i=0;i<n;i++)
    {
        mp[LikeValue[i]].push_back(i+1);//在用户喜好度为LikeValue[i]的时候用户下标为i+1
    }
    //二分法
    int ans = 0;
    for(int j=0;j<q;j++)
    {
        vector<int> p = mp[k[j]];//找到喜好度为k[j]的所有用户的下标
        ans = upper_bound(p.begin(),p.end(),r[j]) - lower_bound(p.begin(), p.end(), l[j]);//上界-下界即为在(l[j],r[j])范围内的用户数量
        printf("%d\n",ans);
    }
    return 0;
}

只考虑整正数的话，下列程序可行

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;

typedef struct Search
{
    int l;
    int r;
    int k;
}Search;
Search search_value[300001];//结构体数组，记录查询组

int main()
{//输入
    int n;//输入用户的个数
    scanf("%d",&n);
    int LikeValue[300001];//每个用户的喜好值
    for(int i=0;i<n;i++)
    {
        scanf("%d",&LikeValue[i]);
    }
    int q;
    scanf("%d",&q);//查询的组数
    for(int j=0;j<q;j++)
    {//每行包含3个整数l,r,k代表一组查询，即标号为l<=i<=r的用户中对这类文章喜好值为k的用户的个数
        scanf("%d%d%d",&search_value[j].l,&search_value[j].r,&search_value[j].k);
    }

    for(int j=0;j<q;j++)
    {
        int count = 0;
        int i = 0;
        while(i<n)
        {
            if(LikeValue[i] >= search_value[j].l && LikeValue[i] <= search_value[j].r)
            {
                if(LikeValue[i] == search_value[j].k)
                {
                    count++;
                }
            }
            i++;
        }
        printf("%d\n",count);
    }
    return 0;
}