hdu 4020 hash的精妙运用

Ads ProposalTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 1537 Accepted Submission(s): 534


Problem DescriptionInputOutputSample InputSample OutputSourceRecommendlcy

题意描述：有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;    }