Problem Solving►UVa

UVa 12382 - Grid of Lamps

Contents

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

Problem

題目網址

N x M 的方格，給你每列和行的燈數，請求出實際的燈數。
注意：不會高估其數量。

Solution

利用行和列的燈數去相抵，以每一列去計算，一一扣掉每一行。

1
2
3
4
5
6
7
8
for (int r = 0; r < n; ++r)
    for (int c = 0; c < m && col[c] && row[r]; ++c)
        if (col[c])
        {
            --col[c];
            --row[r];
            ++sum;
        }

而為了確保最後無法相抵的(即是低估的)，可以放在還沒有放燈的格子，
且不會造成明明有可以相抵的卻去多放的情形，每次都將 col 由大排到小。
(不會高估，所以勢必有位置放)

最後如果 col 中有還沒相抵掉的(即是低估的)，直接將其加上即可。
(不會高估，所以對該行而言，一定有某一列可放)

Code

UVa 12382
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <algorithm>
#include <functional>
#define N 1000
using namespace std;

inline int input()
{
    int n = 0;
    char c;
    while ((c = getchar()) != '\n' && c != ' ')
        n = n * 10 + c - '0';
    return n;
}
int main()
{
    int T;
    int row[N] = {}, col[N] = {};
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        scanf("%d%d ", &n, &m);
        for (int i = 0; i < n; ++i)
            row[i] = input();
        //scanf("%d", &row[i]);

        for (int i = 0; i < m; ++i)
            col[i] = input();
        //scanf("%d", &col[i]);

        sort(col, col + m, greater<int>());

        int sum = 0;
        for (int r = 0; r < n; ++r)
        {

            for (int c = 0; c < m && col[c] && row[r]; ++c)
                if (col[c])
                {
                    --col[c];
                    --row[r];
                    ++sum;
                }

            //確保每次都先從還有缺的 col 開始相抵
            std::sort(col, col + m, greater<int>());

            //加上低估的燈數
            sum += row[r];
        }

        //加上低估的燈數
        for (int c = 0; c < m && col[c]; ++c)
            sum += col[c];

        printf("%d\n", sum);
    }

    return 0;
}