首先我們可以發(fā)現(xiàn)如果錯過了一個加油站，而繼續(xù)往前走的時候沒有油了，可以再假裝之前經(jīng)過加油站的時候加過油

于是我們維護(hù)一個大根堆，表示錯過的加油站是哪些，每當(dāng)沒有油的時候從堆頂取出最大值加上去即可

?

 1 /**************************************************************
 2     Problem: 1747
 3     User: rausen
 4     Language: C++
 5     Result: Accepted
 6     Time:20 ms
 7     Memory:916 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 #include <algorithm>
12 #include <queue>
13  
14 using namespace std;
15 const int N = 1e4 + 5;
16  
17 inline int read();
18  
19 struct data {
20     int w, add;
21      
22     inline void get() {
23         w = read(), add = read();
24     }
25      
26     inline bool operator < (const data &d) const {
27         return w > d.w;
28     }
29 } a[N];
30  
31 int n, tot, ans;
32 priority_queue <int> h;
33  
34 int main() {
35     int i;
36     n = read();
37     for (i = 1; i <= n; ++i) a[i].get();
38     a[0].w = read(), tot = read();
39     sort(a + 1, a + n + 1);
40     a[n + 1].w = 0;
41     for (i = 1; i <= n + 1; ++i) {
42         tot -= (a[i - 1].w - a[i].w);
43         while (tot < 0 && !h.empty()) {
44             ++ans;
45             tot += h.top(), h.pop();
46         }
47         if (tot < 0) {
48             puts("-1");
49             return 0;
50         }
51         h.push(a[i].add);
52     }
53     printf("%d\n", ans);
54     return 0;
55 }
56  
57 inline int read() {
58     static int x;
59     static char ch;
60     x = 0, ch = getchar();
61     while (ch < '0' || '9' < ch)
62         ch = getchar();
63     while ('0' <= ch && ch <= '9') {
64         x = x * 10 + ch - '0';
65         ch = getchar();
66     }
67     return x;
68 }

View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/rausen/p/4480575.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1747 [Usaco2005 open]Expedition 探险的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。