hdu 1896.Stones 解题报告

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1896

题目意思:给出 n 块石头的初始位置和能到达的距离。对于第奇数次遇到的石头才抛掷,偶数次的就忽略。问最多能扔到多远。如果有多颗石头在一个位置,距离小的那个标记为先遇到的。

  所以先解说一下第二个测试案例:

  2

  1  5

  6  6

hdu  1896.Stones   解题报告

在6这个位置的时候,由于5比6小,所以规定1(5)这个点是先遇上的,是偶数次遇到,所以忽略。

  用优先队列做,位置近的优先级越高,如果位置相同,距离短的优先级越高。

  

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; const int maxn = + ;
struct node {
int P, D;
bool operator < (const node& a) const {
return P > a.P || (P == a.P && D > a.D);
}
}; int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE int T, N;
node stone;
priority_queue<node> pq;
while (scanf("%d", &T) != EOF) {
while (T--) {
scanf("%d", &N);
for (int i = ; i < N; i++) {
scanf("%d%d", &stone.P, &stone.D);
pq.push(stone);
}
int ans = ;
int judge = ;
while (!pq.empty()) {
stone = pq.top();
pq.pop();
if (judge) {
stone.P += stone.D;
ans = stone.P;
pq.push(stone);
}
judge = !judge;
}
printf("%d\n", ans);
}
}
return ;
}
上一篇:.net打印控件基本用法


下一篇:项目ITP(四) javaweb http json 交互 in action (服务端 spring 手机端 提供各种工具类)勿喷!