2015
04-15

http://acm.hdu.edu.cn/showproblem.php?pid=4020

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 607    Accepted Submission(s): 234

Problem Description
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

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.

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

#include <iostream>
#include <algorithm>
using namespace std;
const int N =500010;
#define  min(a,b) a<b?a:b
struct node
{
__int64 c,l,u,no;
bool operator<(const node t)const
{
if(u==t.u)
return t.c<c;
return u<t.u;
}
}num[500010];

int cmp(const void *p,const void *q)			//按
{
return (*(node*)p).no-(*(node*)q).no;
}
__int64 ans[N];
int main()
{
int t,n,m,q,i,k,cnt=1;
scanf("%d",&t);
while (t--)
{
scanf("%d%d%d",&n,&m,&q);
for(i=0;i<m;i++)
scanf("%d%d%d",&num[i].u,&num[i].c,&num[i].l);
sort(num,num+m);

// 		printf("\nafter once sort:\n");
// 		for(i=0;i<m;i++)
// 			printf("%I64d %I64d %I64d\n",num[i].u,num[i].c,num[i].l);

num[0].no=0;
int Maxlen=-1;
for(i=1;i<m;i++)
{
if(num[i].u == num[i-1].u)
num[i].no=num[i-1].no+1;
else
num[i].no=0;
if(Maxlen<num[i].no)
Maxlen=num[i].no;
}
qsort(num,m,sizeof(num[0]),cmp);

// 		printf("\nafter twice sort:\n");
// 		for(i=0;i<m;i++)
// 			printf("%I64d %I64d %I64d\n",num[i].u,num[i].c,num[i].l);

//计算出结果
int hh=1;
ans[1]=num[0].l;
for(i=1;i<m;i++)
{
if(num[i].no!=num[i-1].no)
{
ans[hh]+=ans[hh-1];
hh++;
ans[hh]=num[i].l;
}
else
ans[hh]+=num[i].l;
}
ans[hh]+=ans[hh-1];
printf("Case #%d:\n",cnt++);
while (q--)
{
scanf("%d",&k);
k=min(hh,k);
printf("%I64d\n",ans[k]);
}
}
return 0;
}

1. 我说吧，这种圈子里混的人也就这样了，赚不到钱至少得学会理财吧，不过反正别人sb就sb了，他钱爱怎样用那也的确是他的事反正不是用我的钱就对了，纠结这个的确没啥意义。

2. 我说吧，这种圈子里混的人也就这样了，赚不到钱至少得学会理财吧，不过反正别人sb就sb了，他钱爱怎样用那也的确是他的事反正不是用我的钱就对了，纠结这个的确没啥意义。

3. 我说吧，这种圈子里混的人也就这样了，赚不到钱至少得学会理财吧，不过反正别人sb就sb了，他钱爱怎样用那也的确是他的事反正不是用我的钱就对了，纠结这个的确没啥意义。

4. 我说吧，这种圈子里混的人也就这样了，赚不到钱至少得学会理财吧，不过反正别人sb就sb了，他钱爱怎样用那也的确是他的事反正不是用我的钱就对了，纠结这个的确没啥意义。

5. 我说吧，这种圈子里混的人也就这样了，赚不到钱至少得学会理财吧，不过反正别人sb就sb了，他钱爱怎样用那也的确是他的事反正不是用我的钱就对了，纠结这个的确没啥意义。

6. 我说吧，这种圈子里混的人也就这样了，赚不到钱至少得学会理财吧，不过反正别人sb就sb了，他钱爱怎样用那也的确是他的事反正不是用我的钱就对了，纠结这个的确没啥意义。

7. 我说吧，这种圈子里混的人也就这样了，赚不到钱至少得学会理财吧，不过反正别人sb就sb了，他钱爱怎样用那也的确是他的事反正不是用我的钱就对了，纠结这个的确没啥意义。

8. 我说吧，这种圈子里混的人也就这样了，赚不到钱至少得学会理财吧，不过反正别人sb就sb了，他钱爱怎样用那也的确是他的事反正不是用我的钱就对了，纠结这个的确没啥意义。

9. 我说吧，这种圈子里混的人也就这样了，赚不到钱至少得学会理财吧，不过反正别人sb就sb了，他钱爱怎样用那也的确是他的事反正不是用我的钱就对了，纠结这个的确没啥意义。

10. 我说吧，这种圈子里混的人也就这样了，赚不到钱至少得学会理财吧，不过反正别人sb就sb了，他钱爱怎样用那也的确是他的事反正不是用我的钱就对了，纠结这个的确没啥意义。

11. 我说吧，这种圈子里混的人也就这样了，赚不到钱至少得学会理财吧，不过反正别人sb就sb了，他钱爱怎样用那也的确是他的事反正不是用我的钱就对了，纠结这个的确没啥意义。

12. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。