首页 > ACM题库 > HDU-杭电 > hdu 4020-ads proposal-排序-[解题报告]hoj
2015
04-15

hdu 4020-ads proposal-排序-[解题报告]hoj

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

Ads Proposal

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

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.
 

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

题意:有N个客户投资了M个广告,现给出M个广告的信息(所属客户 , 点击量 , 广告长度)

现给Q次查询,每次查询内容为每个客户TOP K 点击量的广告长度之和,即求每个客户前K个点击量最高的广告的总长度

题解:  第一次排序,按客户排序,相同客户所属的广告按点击量高到低排序.

第二次排序其实就是:把所属客户相同的广告做分类标记好每个广告在所属客户中的层次后,把所有广告信息按TOP i 排序.

最后O(N) 线性把答案给打表了.

如果还不明白可以把代码中的注释打印出来看下


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

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  4. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。