HDU 4020 Ads Proposal 简单的模拟

本文主要是介绍HDU 4020 Ads Proposal 简单的模拟，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你n个广告商，他们有一些广告，每个广告都有相应的点击率和长度，现在为你每个广告商的点击率排名前k个的广告的和。

想法：数据不能每查询一次就找一次，那样必定超时，所以在查询之前要进行预处理。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,k;
struct node
{int id,click;__int64 len;
}e[500000+5];
int maxx;
__int64 pp[100000+5];
int mark[100000+5];
bool cmp(node a,node b)
{if(a.id==b.id) return a.click>b.click;else return a.id<b.id;
}
void Input()
{scanf("%d%d%d",&n,&m,&k);maxx=-1;memset(mark,0,sizeof(mark));for(int i=1;i<=m;i++){scanf("%d%d%I64d",&e[i].id,&e[i].click,&e[i].len);mark[e[i].id]++;}for(int i=1;i<=n;i++){if(maxx<mark[i]){maxx=mark[i];}}
} 
void pretreatment(int ca)
{int cnt=1;sort(e+1,e+m+1,cmp);memset(pp,0,sizeof(pp));pp[1]=e[1].len;for(int i=2;i<=m;i++){if(e[i].id!=e[i-1].id){cnt=0;}pp[++cnt]+=e[i].len;}for(int i=2;i<=maxx;i++){pp[i]=pp[i-1]+pp[i];}printf("Case #%d:\n",ca);for(int i=1;i<=k;i++){int p;scanf("%d",&p);if(maxx<p) p=maxx;printf("%I64d\n",pp[p]);}
}
int main()
{int t,ca=1;scanf("%d",&t);while(t--){Input();pretreatment(ca++);}return 0;
}

这篇关于HDU 4020 Ads Proposal 简单的模拟的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---