Tokens on the Segments ZOJ - 4120 （贪心+优先队列）

2019/05/13 20:10

题目链接：https://cn.vjudge.net/problem/ZOJ-4120

AC代码：

 1 #include<bits/stdc++.h>
2 using namespace std;
3 # define ll long long
4 # define inf 0x3f3f3f3f
5 const int maxn = 2e5+100;
6 const int N = 100+10;
7 const ll mod = 998244353;
8 struct node
9 {
10     ll st,ed;
11     node() {}
12     node(ll xx,ll yy)
13     {
14         st=xx,ed=yy;
15     }
16     bool friend operator < (node t1,node t2)
17     {
18         if(t1.st!=t2.st)
19             return t1.st>t2.st;
20         return t1.ed>t2.ed;
21     }
22 };
23 int main()
24 {
25     int T;
26     scanf("%d",&T);
27     while(T--)
28     {
29         int n;
30         ll st,ed;
31         scanf("%d",&n);
32         priority_queue<node>w;
33         for(int i=1; i<=n; i++)
34         {
35             scanf("%lld %lld",&st,&ed);
36             w.push(node(st,ed));
37         }
38         ll maxx=0;
39         int ans=0;
40         while(!w.empty())
41         {
42             node top=w.top();
43             w.pop();
44             if(top.st<=maxx&&top.st+1<=top.ed){
45             w.push(node(top.st+1,top.ed));
46             continue;
47             }
48             if(top.st>maxx)ans++,maxx=max(maxx,top.st);
49         }
50         printf("%d\n",ans);
51     }
52     return 0;
53 }

0
0 收藏

0 评论
0 收藏
0