Problem Solving►UVa

UVa 11292 - Dragon of Loowater

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

看需要多少錢才可殺掉全部的龍，每個騎士只能砍高度比它矮或一樣的龍頭，聘每個騎士的金額為騎士的身高。

Solution

騎士和龍都先排序後，一一比對只要可以砍目前的就聘請他。

Code

UVa 11292
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<algorithm>

int main()
{
    int n, m, k[20000], d[20000];
    while (scanf("%d%d", &n, &m) && n)
    {
        int i;
        for (i = 0; i < n; i++)
            scanf("%d", &d[i]);
        for (i = 0; i < m; i++)
            scanf("%d", &k[i]);

        std::sort(d, d + n);
        std::sort(k, k + m);

        int sum = 0, j = 0;
        for (i = 0; i < n; i++)
        {
            while (j < m&&k[j] < d[i])
                j++;

            if (j == m)
                break;

            sum += k[j++];
        }

        if (i == n)
            printf("%d\n", sum);
        else
            puts("Loowater is doomed!");
    }

    return 0;
}