当前位置: 代码迷 >> 综合 >> uva11292--贪心
  详细解决方案

uva11292--贪心

热度:82   发布时间:2023-11-06 19:25:24.0


题意:

国王要雇骑士去杀龙,每个骑士的收费取决于骑士的高度,每个骑士都能杀死高度小于等于自己的龙,给出龙跟骑士的数量与高度,求最优解。

思路:

将骑士排序,每次杀龙的时候都从最小的开始尝试,直到所有的龙全部杀完。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int lo[21000],qi[21000];
int main(){int n,m;while(cin>>n>>m&&m&&n){for(int i=0;i<n;i++)cin>>lo[i];for(int i=0;i<m;i++)cin>>qi[i];sort(lo,lo+n);sort(qi,qi+m);int sum=0;int flag=1;for(int i=n-1;i>=0&&flag;i--){flag=0;for(int j=0;j<m;j++){if(qi[j]==-1) continue;if(qi[j]>=lo[i]){sum+=qi[j];qi[j]=-1;flag=1;break;}}}if(flag) cout<<sum<<endl;else cout<<"Loowater is doomed!"<<endl;}return 0;}