贪心算法+优先队列。
很明显是应当先消灭blood值大的,那么注意到,对于少blood值的,能灭大blood值的箭必定能消灭小blood值的,所以,可以先排序,在消灭一个blood值的时候,选择一个小Q币的即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define LL __int64
using namespace std;
const int MAXN=100005;
int blood[MAXN];
struct Node{
int p,dam;
bool operator <(const Node &a) const{
if(p>a.p) return true;
return false;
}
}hert[MAXN];
bool cmp1(Node a,Node b){
if(a.dam>b.dam) return true;
return false;
}
bool cmp2(int a,int b){
if(a>b) return true;
return false;
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
priority_queue<Node>que;
for(int i=0;i<n;i++)
scanf("%d",&blood[i]);
for(int i=0;i<m;i++){
scanf("%d",&hert[i].dam);
}
for(int i=0;i<m;i++)
scanf("%d",&hert[i].p);
sort(blood,blood+n,cmp2);
sort(hert,hert+m,cmp1);
LL ans=0;
int j=0;
bool flag=true;
for(int i=0;i<n;i++){
for(;j<m&&hert[j].dam>=blood[i];j++){
que.push(hert[j]);
}
if(que.empty()){
flag=false;
break;
}
ans+=que.top().p;
que.pop();
}
if(!flag){
puts("No");
}
else printf("%I64d\n",ans);
}
return 0;
}
原文:http://www.cnblogs.com/jie-dcai/p/4366950.html