首页 > 试题广场 >

用户喜好

[编程题]用户喜好

热度指数：491 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为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

输入

输出

1
0
2

说明

样例解释:
有5个用户，喜好值为分别为1、2、3、3、5，
第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1
第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0
第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2

算法知识视频讲解

C/C++

布白

#include <iostream>
using namespace std;

int main()
{
    int n, q;
    cin >> n;
    int user[n + 1];
    for (int i = 1; i <= n; i++) cin >> user[i];
    cin >> q;
    int l, r, k;
    while (q--) {
        cin >> l >> r >> k;
        int count = 0;
        for (int i = l; i <= r; i++)
            if (user[i] == k) count++;
        cout << count << endl;
    }

    return 0;
}

编辑于 2018-03-24 15:17:45 回复(0)

C/C++

JQK2020

任意区间都行，不要求不能重复

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 1e6+5;
int a[N],b[N];
vector<int>v[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+n);
    int len=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++){
        int now=lower_bound(b+1,b+1+len,a[i])-b;
        v[now].push_back(i);
    }
    int q;cin>>q;
    while(q--){
        int x,y,z;cin>>x>>y>>z;
        int k=z;
        z=lower_bound(b+1,b+len+1,z)-b;
        if(z==len+1||b[z]!=k){
            cout<<0<<'\n';continue;
        }
        x=lower_bound(v[z].begin(),v[z].end(),x)-v[z].begin();
        y=upper_bound(v[z].begin(),v[z].end(),y)-v[z].begin();
        cout<<y-x<<'\n';
    }
    return 0;
}

发表于 2021-01-10 21:06:35 回复(0)

骑着企鹅去纽约

1、定义喜好值可变数组

2、根据标号的起始和长度获取子数组

3、遍历获取子数据目标值个数

发表于 2020-09-25 12:09:25 回复(0)

kill_LB

#include <stdio.h>

//#include <stdlib.h>

#define N 300000

inthabits(inta[],intstart,intend,intkey);

intmain()

{

intuser[N],scan[3*N];

inti,n,q;//用户喜爱值数组和查询数组（3个为一组）

scanf("%d",&n);

for(i=1;i<=n;i++)

scanf("%d",&user[i]);

scanf("%d",&q);

for(i=1;i<=3*q;i++)

scanf("%d",&scan[i]);//数据输入

for(i=1;i<=3*q;i+=3)

habits(user,scan[i],scan[i+1],scan[i+2]);

return0;

}

inthabits(inta[],intstart,intend,intkey){

inti,sum=0;

for(i=start;i<=end;i++)

if(a[i]==key)

sum++;

printf("%d\n",sum);

returnsum;

}

发表于 2020-08-09 17:34:13 回复(0)

牛客194073601号

在可变字典中存可变数组，喜好值k为key，找到的用户注册时间为value，最后比较的就是value数组中的值是否在那段区间内

发表于 2020-01-11 09:30:05 回复(0)

Dx7d9

    

	importsys



	n =int(sys.stdin.readline().strip())



	b =sys.stdin.readline().strip().split(" ")



	c =int(sys.stdin.readline().strip())



	nums =[]



	fori inrange(int(c)):



	    nums.append(sys.stdin.readline().strip().split(" "))



	 



	fori inrange(len(nums)):



	    last =list(nums[i])



	    ss =b[int(last[0])-1:int(last[1])]



	    print(ss.count(last[2]))