HDU_4020

思路還是比較好想的，進(jìn)行排序再統(tǒng)計(jì)即可，但是不同的處理方式之間存在著時(shí)間的差距。

我后來選擇的方式是，先將所有數(shù)據(jù)的標(biāo)號(hào)r[i]依點(diǎn)擊次數(shù)進(jìn)行排序，然后初始化一個(gè)數(shù)組hash[]=0，hash[i]表示依次遍歷時(shí)customer i出現(xiàn)的次數(shù)，用一個(gè)數(shù)組ans[i]來記錄每個(gè)customer點(diǎn)擊率排行第i的廣告的總的長(zhǎng)度，即在遍歷的時(shí)候令ans[++hash[r[i]]]+=click[r[i]]即可。

最后再用一個(gè)數(shù)組res[i]來表示每個(gè)customer點(diǎn)擊率在第i位及之前的所有廣告的總長(zhǎng)度。

#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;
}

　　

總結(jié)

以上是生活随笔為你收集整理的HDU 4020 Ads Proposal的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。