uva - 11292 - Dragon of Loowater（贪心）

题意：（搬自lrj大大的书）你的国王里边有一条n个头的恶龙，你希望雇佣一些骑士把它杀死，（砍掉所有的头）。村里有m个骑士可以雇佣，一个能力值为x的骑士可以砍掉恶龙一个直径不超过x的头，且需要支付x个金币。要砍掉所有的头，且支付金币最少。

方法：对头的直径和骑士的能力值排序，比较即可。贪心算法。

#include 
  
     
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            using namespace std; #define MAX 20000+10 int head[MAX], warrior[MAX], n, m, sum; void Input() { int i = 0, j = 0; for (i = 0; i < n; i++) cin >> head[i]; for (i = 0; i < m; i++) cin >> warrior[i]; } void Calulate() { int i = 0, j = 0; while (j < m) { if (warrior[j] >= head[i]) { sum += warrior[j], i++, j++; } else { j++; } if (i == n) { cout << sum << endl; return; } } cout << "Loowater is doomed!" << endl; } int main() { #ifdef Local freopen("a.in", "r", stdin); #endif int i = 0, j = 0; while (cin >> n >> m && n+m) { memset(head, 0, sizeof(head)); memset(warrior, 0, sizeof(warrior)); sum = 0; Input(); sort(head, head+n); sort(warrior, warrior+m); Calulate(); } }