「NOIP模拟赛」打地鼠游戏
题目描述：
伟大的2320学长特别喜欢打地鼠游戏，这个游戏开始后，会在地板上冒出一些地鼠来，你可以用榔头去敲击这些地鼠，每个地鼠被敲击后，将会增加相应的游戏分值。可是，所有地鼠只会在地上出现一段时间（而且消失后再也不会出现），每个地鼠都在0时刻冒出，但停留的时间可能是不同的，而且每个地鼠被敲击后增加的游戏分值也可能是不同。
最近2320学长经常玩这个游戏，以至于敲击每个地鼠只要1秒。他在想如何敲击能使总分最大。
输入描述：
输入包含3行，第一行包含一个整数n（1<=n<=100000）表示有n个地鼠从地上冒出来，第二行n个用空格分隔的整数表示每个地鼠冒出后停留的时间（Maxt<=50000），第三行n个用空格分隔的整数表示每个地鼠被敲击后会增加的分值v（v<=1000）。每行中第i个数都表示第i个地鼠的信息。
样例输入：
5
5 3 6 1 4
7 9 2 1 5
样例输出：
24
数据范围：
30%的数据保证n<=100, t<=500,v<=50
60%的数据保证 n<=10000,t<=3000,v<=500
100%的数据保证 n<=100000,t<=5000,v<=1000
题解
这算经典题吧T T
按照时间排序，不断取，直到取得个数超过当前时间，把价值最小的删除
用堆来维护这个过程
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define ll long long #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans,now; struct data{int v,t;}a[100005]; inline bool operator<(data a,data b) { return a.t<b.t; } int main() { //freopen("mouse.in","r",stdin); //freopen("mouse.out","w",stdout); priority_queue<int,vector<int>,greater<int> > heap; n=read(); for(int i=1;i<=n;i++)a[i].t=read(); for(int i=1;i<=n;i++)a[i].v=read(); sort(a+1,a+n+1); for(int i=1;i<=n;i++) { if(now<a[i].t) { now++; ans+=a[i].v; heap.push(a[i].v); } else { int t=heap.top(); if(t>a[i].v)continue; else { ans=ans-t+a[i].v; heap.pop(); heap.push(a[i].v); } } } printf("%d",ans); return 0; } |
Subscribe
计数器 9787635
OI 课件=>
OI 课件=>