Ads Proposal
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 1537 Accepted Submission(s): 534
Problem Description
There are N customers set their M different advertisements on Baidu. Each advertisement is owned by single customer. The ads system of Baidu records the number of clicks of each advertisement this year. The proposal system wants to
analysis the advertisements about the relativity of the description length and the number of clicks of the advertisements. During the analysis, it is very important to do such a query to ask the total length of the advertisements with top k clicking times
for each customer. You may assume the number of clicks of all advertisements are distinct.
Your task is to help Baidu to design this little toolkit.
analysis the advertisements about the relativity of the description length and the number of clicks of the advertisements. During the analysis, it is very important to do such a query to ask the total length of the advertisements with top k clicking times
for each customer. You may assume the number of clicks of all advertisements are distinct.
Your task is to help Baidu to design this little toolkit.
Input
The input consist multiple test cases. The number of test cases is given in the first line of the input.
For each test case, the first line contains three integers N, M and Q, denoting the number customer, the number of advertisement instances and the number of queries. (N <= 100000, M <= 500000, Q <= 100000)
Then M lines follow, each line contains three numbers, U, C and L, indicating the owner of this advertisement, the clicks for this advertisement and the length. (1 <= U <= N, 0 <= C, L <= 1000000000)
Finally Q lines come. Each line contains only one integer k, representing the query for top k clicking advertisements for each customer.
For each test case, the first line contains three integers N, M and Q, denoting the number customer, the number of advertisement instances and the number of queries. (N <= 100000, M <= 500000, Q <= 100000)
Then M lines follow, each line contains three numbers, U, C and L, indicating the owner of this advertisement, the clicks for this advertisement and the length. (1 <= U <= N, 0 <= C, L <= 1000000000)
Finally Q lines come. Each line contains only one integer k, representing the query for top k clicking advertisements for each customer.
Output
For each test case, output Q lines, each line contains only one integer, denoting the sum of total length of the top k number of clicks for each customer.
Sample Input
2 2 4 3 1 12 13 2 23 41 1 21 46 1 22 31 1 2 3 6 15 3 5 2677139 731358928 2 347112028 239095183 6 27407970 85994789 6 767687908 734935764 6 255454855 110193353 3 39860954 813158671 5 617524049 55413590 3 338773814 7907652 6 810348880 736644178 2 777664288 63811422 6 590330120 616490361 5 552407488 136492190 1 416295130 448298060 5 811513162 232437061 4 43273262 874901209 4 9 13
Sample Output
Case #1: 72 118 131 Case #2: 5801137622 5887132411 5887132411
Source
Recommend
lcy
题意描述：有n个顾客，m个广告，每个顾客可以有多个广告，每个广告有一个点击量和长度，现在要求每个顾客前k个访问量的长度总和的总和
思路 ：hash
不要对每个k去求 然后相加 应该在程序中打表 找出所有的 直接对应输出
先将所有数据的标号r[i]依点击次数进行排序，然后初始化一个数组hash[]=0，
hash[i]表示依次遍历时customer i出现的次数，
用一个数组ans[i]来记录每个customer点击率排行第i的广告的总的长度，
即在遍历的时候令ans[++hash[r[i]]]+=click[r[i]]即可。
最后再用一个数组res[i]来表示每个customer点击率在第i位及之前的所有广告的总长度。
http://blog.csdn.net/hnust_xiehonghao/article/details/8279267 这是另外一种方法
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int N,M,Q,U,C,L;
int name[500110],r[500110],q;
double click[500010],len[500110];
double ans[500110],res[500110];
int hash[100110];
int cmp(const void *_p,const void *_q)
{
int *a=(int *)_p;
int *b=(int *)_q;
return click[*a]>click[*b]?-1:1;
}
int main()
{
int i,j,k,n,t,tt,cur;
scanf("%d",&t);
for(tt=0;tt<t;tt++)
{
scanf("%d%d%d",&N,&M,&Q);
for(i=0;i<M;i++)
{
scanf("%d%lf%lf",&name[i],&click[i],&len[i]);
r[i]=i;
}
qsort(r,M,sizeof(r[0]),cmp);
for(i=1;i<=N;i++)
hash[i]=0;
for(i=1;i<=M;i++)
ans[i]=0.0;
for(i=0;i<M;i++)
{
hash[name[r[i]]]++;
ans[hash[name[r[i]]]]+=len[r[i]];
}
res[0]=0;
for(i=1;i<=M;i++)
{
res[i]=ans[i]+res[i-1];
}
printf("Case #%d:\n",tt+1);
for(i=0;i<Q;i++)
{
scanf("%d",&q);
if(q>M)
printf("%.0f\n",res[M]);
else
printf("%.0f\n",res[q]);
}
}
return 0;
}