首页 > 代码库 > hihocoder 1306

hihocoder 1306

http://hihocoder.com/problemset/problem/1306

 

题目不难,主要是我在这里学会了set的用法,其实set是可以根据自己的需求去排序的,这样还是很方便的

set<int,greater<int>>s;

这样就是对于int升序排序

这个题的主要思路也就是说

用set来记录prime和time,按照prime来排序,然后每次查询只需要查询set的两端就可以了,如果之前被删了,则删除就行,复杂度还是比较低的

 1 #include <set>
 2 #include <iostream>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 struct RatioComp {   //排序
 7     bool operator() (const pair<int, int>& A, const pair<int, int>& B) {
 8         if(A.first==B.first )
 9             return A.second<B.second;
10         return A.first<B.first;
11     }
12 };
13 
14 int main()
15 {
16    // freopen("in.txt","r",stdin);
17     set<pair<int,int>,RatioComp>s;
18     int m,a,b;
19     char c;
20     cin >> m;
21     int tmp;
22     int dele = 0;
23     while (m--)
24     {
25         cin >> c;
26         if (c == P)
27         {
28             cin >> a >> b;
29             s.insert(make_pair(b, a));
30             tmp = b;
31         }else if (c == R)
32         {
33             cin >> a;
34             if (a > dele)
35                 dele = a;
36         }
37         else {
38             set<pair<int,int> >::iterator iter = s.end();
39             iter--;
40             while(iter!=s.begin())
41             {
42                 if (iter->second<= dele)
43                     s.erase(iter--);
44                 else
45                     break;
46             }
47            cout << iter->first <<" ";
48             iter = s.begin();
49             while (iter != s.end())
50             {
51                 if (iter->second<= dele)
52                     s.erase(iter++);
53                 else break;
54             }
55             cout << iter->first << " " << tmp << endl;
56         }
57     }
58     return 0;
59 }

 

hihocoder 1306