#UVa:11292-Dragon of Loowater

灆洢 2016-04-20 02:26:23

將龍的頭高和騎士身高從小到大排好,由於一個騎士只能砍一個龍頭,所以就在兩個排序好的數列一個一個對讓龍頭給最矮能夠砍它的騎士砍即是答案。

C++(0.000)

/*******************************************************/
/* UVa 11292 Dragon of Loowater                        */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2016/04/20                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
  int n, m;
  while( scanf("%d%d", &n, &m) != EOF && n != 0 && m != 0 ){
    vector<int> dragonHeads(n);
    vector<int> knightHeights(m);

    for( int i = 0 ; i < n ; ++i ){
      scanf("%d", &dragonHeads[i]);
    }

    for( int i = 0 ; i < m ; ++i ){
      scanf("%d", &knightHeights[i]);
    }

    sort(dragonHeads.begin(), dragonHeads.end());
    sort(knightHeights.begin(), knightHeights.end());

    int cost = 0;
    int i, j;
    for( i = 0, j = 0 ;
         i < dragonHeads.size() && j < knightHeights.size() ; ){
      if( dragonHeads[i] <= knightHeights[j] ){
        cost += knightHeights[j];
        ++i;
        ++j;
      }
      else {
        ++j;
      }
    }

    if( i != dragonHeads.size() ){
      printf("Loowater is doomed!\n");
    }
    else{
      printf("%d\n", cost);
    }

  }
  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料