P2278 [HNOI2003]操作系统

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 
 5 #define debug(a) cout<<"debug: "<<a<<endl
 6 
 7 struct Pro
 8 {
 9     int num, re, us, le;
10     bool operator <(Pro s)const
11     {
12         if (le == s.le) return num > s.num;
13         return le < s.le;
14     }
15 }p[500010];
16 
17 int n;
18 priority_queue<Pro>q;
19 
20 int main()
21 {
22     ios::sync_with_stdio(0);
23     while (cin >> p[++n].num >> p[n].re >> p[n].us >> p[n].le);
24     n--;
25     for (int i = 1; i <= n; i++)
26     {
27         if (q.empty())
28         {
29             q.push(p[i]);
30             continue;
31         }
32         while (!q.empty() && q.top().re + q.top().us <= p[i].re)
33         {
34             Pro temp = q.top();
35             cout << q.top().num << " " << temp.re + temp.us << endl;
36             q.pop();
37             if (!q.empty())
38             {
39                 Pro t = q.top();
40                 t.re = temp.re + temp.us;
41                 q.pop();
42                 q.push(t);
43             }
44         }
45         if (!q.empty() && q.top().le < p[i].le)
46         {
47             Pro t = q.top();
48             q.pop();
49             t.us -= p[i].re - t.re;
50             t.re = p[i].re;
51             q.push(t);
52         }
53         q.push(p[i]);
54     }
55     while (!q.empty())
56     {
57         Pro temp = q.top();
58         cout << q.top().num << " " << temp.re + temp.us << endl;
59         q.pop();
60         if (!q.empty())
61         {
62             Pro t = q.top();
63             t.re = temp.re + temp.us;
64             q.pop();
65             q.push(t);
66         }
67     }
68 }