HDU4544 湫湫系列故事――消滅兔子

Tags: 數據結構，貪心

Analysis:

將兔子的血量從大到小排序，將箭的殺傷力從大到小排序，對於每一個兔子血量，

將比他大的殺傷力大的劍壓入優先隊列，優先隊列自己重寫，讓它每次拋出的數為價錢最小。

Code:

[cpp] view plaincopyprint?
#include <cstdio>   
#include <queue>   
#include <algorithm>   
#include <functional>   
using namespace std;  
typedef long long LL;  
const int maxn = 100010;  
struct tt {  
     int d;  
     int p;  
     bool operator <(const tt& t) const {  
          return d>t.d||(d==t.d&&p<t.p);  
     }  
} pt[maxn];  
int b[maxn];  
priority_queue<int , vector<int>, greater<int> > q;  
int main()  
{  
     int n, m, i, j;  
     while(~scanf("%d%d",&n,&m)) {  
          for(i=1; i<=n; i++) scanf("%d",&b[i]);  
          for(i=1; i<=m; i++) scanf("%d",&pt[i].d);  
          for(i=1; i<=m; i++) scanf("%d",&pt[i].p);  
          sort(b+1,b+1+n,greater<int>());  
          sort(pt+1,pt+1+m);  
          while(!q.empty()) q.pop();  
          LL ans = 0;  
          bool flag = 1;  
          for(i=1,j=1; i<=n; i++) {  
               while(j<=m&&pt[j].d>=b[i]) {  
                    q.push(pt[j].p);  
                    j++;  
               }  
               if(!q.empty()) {  
                    ans += q.top();  
                    q.pop();  
               } else {  
                    flag = 0;  
                    break;  
               }  
          }  
          if(flag) printf("%I64d\n",ans);  
          else printf("No\n");  
     }  
     return 0;  
}