Description

湫湫減肥
　　越減越肥！
　　
　　最近，減肥失敗的湫湫為發泄心中郁悶，在玩一個消滅免子的游戲。
　　游戲規則很簡單，用箭殺死免子即可。
　　箭是一種消耗品，已知有M種不同類型的箭可以選擇，并且每種箭都會對兔子造成傷害，對應的傷害值分別為Di（1 <= i <= M），每種箭需要一定的QQ幣購買。
　　假設每種箭只能使用一次，每只免子也只能被射一次，請計算要消滅地圖上的所有兔子最少需要的QQ幣。

Input

輸入數據有多組，每組數據有四行；
第一行有兩個整數N，M（1 <= N, M <= 100000），分別表示兔子的個數和箭的種類；
第二行有N個正整數，分別表示兔子的血量Bi（1 <= i <= N）；
第三行有M個正整數，表示每把箭所能造成的傷害值Di（1 <= i <= M）；
第四行有M個正整數，表示每把箭需要花費的QQ幣Pi（1 <= i <= M）。

特別說明：
1、當箭的傷害值大于等于兔子的血量時，就能將兔子殺死；
2、血量Bi，箭的傷害值Di，箭的價格Pi，均小于等于100000。

Output

如果不能殺死所有兔子，請輸出”No”，否則，請輸出最少的QQ幣數，每組輸出一行。

Sample Input

3 3 1 2 3 2 3 4 1 2 3 3 4 1 2 3 1 2 3 4 1 2 3 1

Sample Output

6 4

AC代碼：

#include<bits/stdc++.h> using namespace std; int N,M; int b[100010]; struct node{int d,p; }a[100010]; struct cmp1{bool operator()(int x,int y){return x>y;} }; int cmp(node x,node y){return x.d<y.d; } int main() {int i,j,k;long long ans;while(~scanf("%d %d",&N,&M)){priority_queue<int,vector<int>,cmp1>q;for(i=0;i<N;i++)scanf("%d",&b[i]);for(i=0;i<M;i++)scanf("%d",&a[i].d);for(i=0;i<M;i++)scanf("%d",&a[i].p);if(N>M)cout<<"No"<<endl;else {sort(b,b+N);sort(a,a+M,cmp);int t=M-1,f=0;ans=0;for(i=N-1;i>-1;i--){while(t>-1&&a[t].d>=b[i]){q.push(a[t].p);t--;}if(q.empty()){f=1;break;}ans+=q.top();q.pop();}if(f==1)cout<<"No"<<endl;else cout<<ans<<endl;}}return 0; }

總結

以上是生活随笔為你收集整理的湫湫系列故事——消灭兔子（优先队列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。