#UVa:11292-Dragon of Loowater

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

C++(0.000)

/*******************************************************/
/* UVa 11292 Dragon of Loowater                        */
/* Author: LanyiKnight [at] knightzone.org             */
/* 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;
}

沒有迴響

本文還沒有迴響,快來搶頭香!

發表迴響