BZOJ1747 [Usaco2005 open]Expedition 探险

首先我们可以发现如果错过了一个加油站，而继续往前走的时候没有油了，可以再假装之前经过加油站的时候加过油

于是我们维护一个大根堆，表示错过的加油站是哪些，每当没有油的时候从堆顶取出最大值加上去即可

 /**************************************************************

     Problem: 1747

     User: rausen

     Language: C++

     Result: Accepted

     Time:20 ms

     Memory:916 kb

 ****************************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <queue>

 using namespace std;

 const int N = 1e4 + ;

 inline int read();

 struct data {

     int w, add;

     inline void get() {

         w = read(), add = read();

     }

     inline bool operator < (const data &d) const {

         return w > d.w;

     }

 } a[N];

 int n, tot, ans;

 priority_queue <int> h;

 int main() {

     int i;

     n = read();

     for (i = ; i <= n; ++i) a[i].get();

     a[].w = read(), tot = read();

     sort(a + , a + n + );

     a[n + ].w = ;

     for (i = ; i <= n + ; ++i) {

         tot -= (a[i - ].w - a[i].w);

         while (tot <  && !h.empty()) {

             ++ans;

             tot += h.top(), h.pop();

         }

         if (tot < ) {

             puts("-1");

             return ;

         }

         h.push(a[i].add);

     }

     printf("%d\n", ans);

     return ;

 }

 inline int read() {

     static int x;

     static char ch;

     x = , ch = getchar();

     while (ch < '' || '' < ch)

         ch = getchar();

     while ('' <= ch && ch <= '') {

         x = x *  + ch - '';

         ch = getchar();

     }

     return x;

 }