D. Stones
Time Limit:3000ms
Case Time Limit:3000ms
Memory Limit:32768KB
Font Size:
+
-
Because of the wrong status of the bicycle, Sempr begin to walk east to west every morning and walk back every evening. Walking may cause a little tired, so Sempr always play some games this time.
There are many stones on the road, when he meet a stone, he will throw it ahead as far as possible if it is the odd stone he meet, or leave it where it was if it is the even stone. Now give you some informations about the stones on the road, you are to tell
me the distance from the start point to the farthest stone after Sempr walk by. Please pay attention that if two or more stones stay at the same position, you will meet the larger one(the one with the smallest Di, as described in the Input) first.
Input
In the first line, there is an Integer T(1<=T<=10), which means the test cases in the input file. Then followed by T test cases.
For each test case, I will give you an Integer N(0<N<=100,000) in the first line, which means the number of stones on the road. Then followed by N lines and there are two integers Pi(0<=Pi<=100,000) and Di(0<=Di<=1,000) in the line, which means the position
of the i-th stone and how far Sempr can throw it.
Output
Just output one line for one test case, as described in the Description.
Sample Input
Sample Output
这道题其实就是优先队列的运用。要注意一下优先队列的使用。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
struct node
{
int p,d;
friend bool operator <(node s, node v)
{
if (s.p!=v.p) return s.p>v.p;
return s.d>v.d;
}
};
int main ()
{
int t,n,i,j;
cin>>t;
while(t--)
{
cin>>n;
node e;
priority_queue<node> q;
for (i=0; i<n; i++)
{
scanf("%d%d",&e.p,&e.d);
q.push(e);
}
int k=1,max=0;
while(!q.empty())
{
e=q.top();
q.pop();
if (k%2)
{
e.p=e.d+e.p;
if (e.p>max) max=e.p;
q.push(e);
}
k++;
}
cout<<max<<endl;
}
return 0;
}
分享到:
相关推荐
poj 2978 Colored stones.md
zoj 2634 Collecting Stones.md
Edition 2007-01-09 top secret / strictly confidential page 2 of 520 Contents 1. Intro.................................................................................................................
外研一起小学英语五下《Module6Unit 1 We’ ll see lots of very big stones.》word教案.docx
RECOVERY OF BACILLUS FECALIS ALKALIGENES FROM GALL STONES
资源来自pypi官网。 资源全名:stones-0.1.2-py3-none-any.whl
NULL 博文链接:https://orangered3stones.iteye.com/blog/1496616
Throwing Stones at the (Data Center) Perimeter Walls......Page 15 Limiting Lateral Movement within the Data Center......Page 21 Visibility and context......Page 23 Isolation......Page 24 Segmentation....
Goliath 是一个开源的非堵塞(异步) 的 Ruby Web 服务器框架,由 PostRank 开发。它是一个轻量级的框架提供高性能、Rack API 和中间件支持,配置简单,完全异步处理... Watch out for stones. 标签:Goliath
of those things have served as stepping stones into further research.Some of that research has found its way into presentations I’ve given at various confer- ences,and from there,others have asked ...
5 magic stones ? 4 rocks ? 3 rockborders ? 4 crystals ? 1 dragon skull ? 1 meteorite ? 1 volcano ? 5 particles + 15 free sky textures Check out the demo scene that showcases some of the props in ...
Orchard是一个以微软为主导的开源CMS项目,它允许使用者在.Net平台上快速建立网站,并且提供扩展框架能够允许定制人员通过模块和主题等增加额外的内容,Orchard能够建设出复杂的内容管理系统,它提供了强大的模块化...
石头 在 Sass(和 Coffee)中构建的模块化 css 框架内容安装手动安装下载并复制stones.css或stones.sass文件并将其添加到您的项目文件夹中。 查看来自定义编译的 css。鲍尔通过将 Stones stones-css添加到应用程序的...
题目大意在二维坐标的整数坐标点上,有一些石头,如果一个石头和另外一个石头的横坐标或者纵坐标相等,那么认为他们是有链接的。解题方法并查集这个题翻译一下就是,横或者
Linux程序设计(第4版)附件只有随书的源代码,[英]Neil Matthew, Richard Stones著.陈健,宋健建 译。人民邮电出版社
Use stones to hit blocks and other shapes of obstacles. Then throw bought into the small house. A package is delivered. Try to hit stars and dogs, they have higher score than normal obstacles. This ...
最新版,unity2019亲测可用,无报错
作者: (英)Neil Matthew Richard Stones [作译者介绍] 译者: 陈健 宋健建 丛书名: 图灵程序设计丛书 操作系统 出版社:人民邮电出版社 ISBN:9787115228215 上架时间:2010-6-11 出版日期:2010 年6月 开本:...
作者: (英)Neil Matthew Richard Stones [作译者介绍] 译者: 陈健 宋健建 丛书名: 图灵程序设计丛书 操作系统 出版社:人民邮电出版社 ISBN:9787115228215 上架时间:2010-6-11 出版日期:2010 年6月 开本:...