XYNUOJ 1257: 捕杀恶龙

╰+攻爆jí腚メ 2024-02-18 22:04 24阅读 0赞

### **1257: 捕杀恶龙** ###

时间限制: 1 Sec 内存限制: 128 MB  
提交: 119 解决: 55  
您该题的状态：**已完成**  
\[[提交][Link 1]\]\[[状态][Link 2]\]\[[讨论版][Link 3]\]

### **题目描述** ###

动物园有一条n个头的恶龙，你希望雇佣一些骑士把它杀死（也就是砍掉所有的头）。现在有m个骑士可以雇佣，一个能力值为 x 的骑士可以砍掉恶龙一个直径不超过 x 的头，且需要支付 x 个金币。如何雇佣骑士才能砍掉恶龙所有的头，并且支付最小的金币？（注意：一个骑士只能砍一个头并且仅能被雇佣1次。）

### **输入** ###

输入多组数据，第一行二个整数n、m，（1<=n,m<=20000）;以下n行每行为一个整数，即恶龙每个头的直径，以下m行为一个整数，即每个骑士的能力。输入结束标志为n=m=0.

### **输出** ###

对于每组数据，输出最少花费。如果无解，输出：“Loowater is doomed!”

提示：因为要保证用的钱最少，所以先把骑士按照能力值从小到大进行排序。然后从最小的开始一个一个进行匹配。

### **样例输入** ###

2 3
 5
 4
 7
 8
 4
 2 1
 5
 5
 10
 0 0

### **样例输出** ###

11
 Loowater is doomed!

### **提示** ###

### **来源** ###

[贪心][Link 4]

我刷的好慢啊，但我不会放弃，沉稳、冷静。仔细分析题，相信你自己，加油！

\#include<iostream> 
\#include<algorithm> 
\#include<cstdlib> 
using namespace std; 
int cmp(int x,int y) 
\{ 
return x>y; 
\} 
int main() 
\{ 
int n,m; 
while(~scanf("%d%d",&n,&m),m||n) 
\{ 
int a\[n\],b\[m\]; 
int i,j,k,t=0,sum=0,f=0; 
for(i=0;i<n;i++) 
cin>>a\[i\]; 
for(i=0;i<m;i++) 
cin>>b\[i\]; 
sort(a,a+n,cmp); //对恶龙的头从大到小进行排序 
sort(b,b+m); //对骑士的能力从小到大进行排序 
if(n>m) 
\{ 
cout<<"Loowater is doomed!"<<endl; 
continue; 
\} 
 
/\*for(i=0;i<n;i++) 
cout<<a\[i\]<<" "; 
cout<<endl; 
 
for(i=0;i<m;i++) 
cout<<b\[i\]<<" "; 
cout<<endl; 
\*/ 
for(i=0;i<m;i++) 
\{ 
for(j=0;b\[i\]<a\[j\]&&j<n;j++); 
if(a\[j\]>0) 
\{ 
sum+=b\[i\]; 
a\[j\]=0; 
b\[i\]=0; 
//cout<<" "<<a\[j\]<<" "<<sum<<endl; 
f=j; 
\} 
sort(a,a+n,cmp); 
 
\} 
for(i=0;i<n;i++) 
t+=a\[i\]; 
if(t==0) 
cout<<sum<<endl; 
else 
cout<<"Loowater is doomed!"<<endl; 
 
\} 
return 0; 
\}

再沾一个代码写的好的

`#include<iostream>`

`#include<algorithm>`

`#include<memory.h>`

`using` `namespace` `std;`

`int` `main ( ) {`

```int` `a[20000], b[20000], i, j, payment, N, n, m;``//a, b分别存储巨龙的头的直径和骑士的能力`

```while` `(``scanf` `(``"%d %d"``, &m, &n ) && ( m || n ) )``//m n 分别是巨龙的头的数量和骑士的数量`

```{`

```memset` `( a, 0, 20000 *``sizeof` `(``int` `) );`

```memset` `( b, 0, 20000 *``sizeof` `(``int` `) );`

```for` `( i = 0; i < m; i ++ )`

```{`

```scanf` `(``"%d"``, &a[i] );`

```}`

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

```{`

```scanf` `(``"%d"``, &b[i] );`

```}`

```sort ( a, a + m );`

```sort ( b, b + n );`

```payment = 0;`

```for` `( j = 0, i = 0; i < m && j < n; )`

```{`

```for` `( j; j < n; j ++ )`

```{`

```if` `( b[j] >= a[i] )`

```{`

```payment += b[j];`

```j ++;`

```i ++;`

```break``;`

```}`

```if` `( i < m )`

```{`

```printf` `(``"Loowater is doomed!\n"` `);`

```}`

```else`

```{`

```printf` `(``"%d\n"``, payment );`

```}`

```return` `0;`

`}`

[Link 1]: http://xyoj.xynu.edu.cn/submitpage.php?id=1257
[Link 2]: http://xyoj.xynu.edu.cn/problemstatus.php?id=1257
[Link 3]: http://xyoj.xynu.edu.cn/bbs.php?pid=1257
[Link 4]: http://xyoj.xynu.edu.cn/problemset.php?search=%E8%B4%AA%E5%BF%83