HDOJ 1896 Stones解題報告
14765 ワード
タイトル分類:優先キュー+STL
作者:ACShiryu
解答時間:2011-7-18
Stones
Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 217 Accepted Submission(s): 107
Problem Description
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
Output
Just output one line for one test case, as described in the Description.
Sample Input
2
2
1 5
2 4
2
1 5
6 6
Sample Output
11
12
道にはたくさんの石があって、奇数の序列の石に出会ったら彼を前にして、偶数の不動の彼、もし2つの石が一緒にいたら、先に比較的近い石がまだ比較的大きい石であることを考えて、このようにずっと下りて、前のすべての石がまだ残ってはいけないまで、最も遠い石の距離の起点のどれだけの問題を求めますこの問題は優先的な列でとても便利です.
分析;1つの構造体を定義して、石の現在の位置と外に出られる距離を優先キューにそれぞれ格納し、「最小」を取るたびに偶数個を取得すると動かず、奇数個を取得するとその石の位置を更新して優先キューに再格納し、キューが空になるまで最後の石の位置を出力する
データ分析:プログラムの時間複雑度はO(nlogn)で、データ量は最大100000で、タイムアウトはありません.特に複数の石のxのような場合は、y値が一番小さい石を優先します
参照コード:
作者:ACShiryu
解答時間:2011-7-18
Stones
Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 217 Accepted Submission(s): 107
Problem Description
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
Output
Just output one line for one test case, as described in the Description.
Sample Input
2
2
1 5
2 4
2
1 5
6 6
Sample Output
11
12
道にはたくさんの石があって、奇数の序列の石に出会ったら彼を前にして、偶数の不動の彼、もし2つの石が一緒にいたら、先に比較的近い石がまだ比較的大きい石であることを考えて、このようにずっと下りて、前のすべての石がまだ残ってはいけないまで、最も遠い石の距離の起点のどれだけの問題を求めますこの問題は優先的な列でとても便利です.
分析;1つの構造体を定義して、石の現在の位置と外に出られる距離を優先キューにそれぞれ格納し、「最小」を取るたびに偶数個を取得すると動かず、奇数個を取得するとその石の位置を更新して優先キューに再格納し、キューが空になるまで最後の石の位置を出力する
データ分析:プログラムの時間複雑度はO(nlogn)で、データ量は最大100000で、タイムアウトはありません.特に複数の石のxのような場合は、y値が一番小さい石を優先します
参照コード:
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 #include<cstring>
5 #include<algorithm>
6 #include<cmath>
7 #include<queue>
8 using namespace std;
9 struct Stone{
10 int x; //
11 int y; //
12 };
13 bool operator<( Stone a, Stone b )
14 { // ， x ， x ， y //
15 if( a.x== b.x ) return a.y > b.y;
16 return a.x > b.x;
17 }
18 int main()
19 {
20 int t;
21 scanf("%d",&t);//
22 while(t--)
23 {
24 int n;
25 int i ;
26 priority_queue<Stone>que; // Stone //
27 scanf("%d",&n);
28 Stone tmp;
29 for(i =0;i< n ; i++ )
30 {
31 scanf("%d%d",&tmp.x,&tmp.y);
32 que.push(tmp);//
33 }
34 int sum =1;//
35 while(!que.empty())// ， //
36 {
37 tmp = que.top();// ， //
38 que.pop();//
39 if(sum%2)
40 {// ， ，
41 tmp . x+=tmp.y;// y
42 que.push(tmp);//
43 }
44 sum++;// +1
45 }
46 printf("%d
",tmp.x);// //
47 }
48 return 0;
49 }