打地鼠游戏(堆维护)
2018-07-25 13:00:46来源:博客园 阅读 ()
伟大的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
题解:
首先开一个队列,并让这个队列像堆结构一样工作,采用最小元素放在堆顶的方式。然后对录入的数据进行暗时间从小到大排列,接着开始让第一个分值进入堆,用sum记录总值,用time来卡时间,当一个时间被卡住时,将堆顶分值与当前分值比较,如果小于,推出堆顶数据,将当前分值放入。
tips:队列头文件:#include<queue>
堆排序:priority_queue<
int
,vector<
int
>,greater<
int
> > heap;
推出:
heap.pop();
堆顶:heap.top();
置入:heap.push();
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 struct node 7 { 8 int x,y; 9 }a[1000001]; 10 bool cmp(node o,node p) 11 { 12 return o.x<p.x; 13 } 14 int main() 15 { 16 int sum=0,tim=0; 17 int n,i,top; 18 cin>>n; 19 priority_queue<int,vector<int>,greater<int> > heap; 20 for(i=0;i<n;i++) 21 { 22 cin>>a[i].x; 23 } 24 for(i=0;i<n;i++) 25 { 26 cin>>a[i].y; 27 } 28 sort(a,a+n,cmp); 29 for(i=0;i<n;i++) 30 { 31 if(tim<a[i].x) 32 { 33 tim++; 34 heap.push(a[i].y); 35 sum+=a[i].y; 36 } 37 else 38 { 39 top=heap.top(); 40 if(top<a[i].y) 41 { 42 heap.pop(); 43 heap.push(a[i].y); 44 sum+=a[i].y; 45 sum-=top; 46 } 47 } 48 } 49 cout<<sum<<endl; 50 }
?
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C语言实现经典游戏——扫雷! 2020-04-17
- 小游戏二之---------------五子棋 2020-03-23
- Qt5小Demo之猜数字游戏 2020-03-19
- [Uva1637][DFS][记忆化] 纸牌游戏 Double Patience 2020-03-06
- 游戏终端服务器分享(1.2版) 2020-02-11
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash