BZOJ1555 KD之死

如果没有必选的限制条件，就是水题了、、、

只要按照w + t排序就可以了，然后搞个堆来维护

于是有了限制条件，还是水题。。。

到了必选的时候强制选上，不加入堆中即可。

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

     Problem: 1555

     User: rausen

     Language: C++

     Result: Accepted

     Time:2228 ms

     Memory:10948 kb

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

 #include <cstdio>

 #include <cctype>

 #include <algorithm>

 #include <queue>

 using namespace std;

 typedef long long ll;

 const int N  = ;

 struct data {

     int w, t, f;

 }a[N];

 bool operator < (const data &a, const data &b) {

     return (ll) a.w + a.t < (ll) b.w + b.t;

 }

 ll tot, V;

 int n, m, w, ans;

 priority_queue <int> q;

 inline ll read() {

     ll x = ;

     char ch = getchar();

     while (!isdigit(ch))

         ch = getchar();

     while (isdigit(ch)) {

         x = x *  + ch - '';

         ch = getchar();

     }

     return x;

 }

 inline void del_top() {

     tot -= q.top(), q.pop();

     --ans;

 }

 inline void add(int x) {

     tot += a[x].w, q.push(a[x].w);

     ++ans;

 }

 bool work() {

     int i;

     tot = ;

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

         if (a[i].f == ) {

             while (tot > a[i].t) {

                 if (q.empty()) return ;

                 del_top();

             }

             tot += a[i].w, ++ans;

         }else {

             if (!q.empty() && tot > a[i].t)

                 if (q.top() < a[i].w || tot - q.top() > a[i].t)

                     continue;

             if (tot > a[i].t)

                 del_top();

             add(i);

         }

     return ;

 }

 int main() {

     int i, X;

     n = read(), m = read(), V = read();

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

         a[i].w = read(), a[i].t = read();

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

         X = read(), a[X].f = ;

         tot += a[X].w;

     }

     sort(a + , a + n + );

     a[++n].f = , a[n].t = V;

     if (!work()) puts("Foolish SD!");

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

     return ;

 }

（p.s. 怎么又想开fread二笔优化了呢、、、233）