题解 UVA11292 【Dragon of Loowater】

思路与楼上一样,但是代码更短 (按照蓝书打的)光速逃

能力强的武士开价高是合理的,但如果你派去看一个很弱的头,那就是浪费人才了。可以把骑士按照能力从小到大排序,所有头直径排排序,就$OK$了!

PS:这就是greedy algorithm
(贪心算法,逃)

#include<cstdio>
#include<algorithm>       // 因为用到了sort
using namespace std;

const int maxn = 20000 + 5;
int A[maxn], B[maxn];
int main() {
  int n, m;
  while(scanf("%d%d", &n, &m) == 2 && n && m) {
    for(int i = 0; i < n; i++) scanf("%d", &A[i]);
    for(int i = 0; i < m; i++) scanf("%d", &B[i]);
    sort(A, A+n);
    sort(B, B+m);
    int cur = 0;         // 当前需要砍掉的头的编号
    int cost = 0;        // 当前总费用
    for(int i = 0; i < m; i++)
      if(B[i] >= A[cur]) {
        cost += B[i];           // 雇佣该骑士
        if(++cur == n) break;   // 如果头已经砍完,及时退出循环
      }
    if(cur < n) printf("Loowater is doomed!\n");
    else printf("%d\n", cost);
  }
  return 0;
}

添加新评论

请不要水评论

评论列表