「牛客 CSP-S 模拟赛」光 - 二分答案

发表于 分类于 ， 阅读次数： Disqus：

题意描述

牛客链接（需付费）

在一个 \(2 \times 2\) 的网格上有四盏灯，每个网格一盏。这四盏灯的位置分别是左上角，右上角，左下角，右下角。

每盏灯有一个可供调节的耗电量，耗电量越高，则灯对周围提供的亮度越多。具体来说，若某一盏灯的耗电量为 \(x\)，那么它将会为自己的格子提供 \(x\) 的亮度，为相邻的两个格子提供 \(\lfloor \frac{x}{2} \rfloor\) 的亮度，为对角的格子提供 \(\lfloor \frac{x}{4} \rfloor\)。其中 \(\lfloor x \rfloor\) 表示对 \(x\) 向下取整。

某一个格子的亮度是四盏灯对它提供的亮度之和。例如左上角的灯耗电量为 \(4\)，右上角的灯耗电量为 \(7\)，右下角的灯耗电量为 \(8\)，左下角的灯耗电量为 \(0\)，那么左上角这个格子的亮度就是 \(4 + \lfloor \frac{7}{2} \rfloor + \lfloor \frac{8}{4} \rfloor + 0 = 9\)

现在我们对 四个格子的最低亮度 提出了要求，我们想要让四个格子的亮度都达到标准。你可以将每一盏灯的耗电量调节为任何一个大于等于零的整数，为了省电，你希望四盏灯的耗电量之和尽可能的小，请问 四盏灯的最小耗电量之和 是多小？

数据范围：四个格子的最低亮度均为正整数且不超过 \(1500\)。

解题思路

本题由于直接算出四个格子的耗电量较为困难，可考虑二分答案，二分总耗电值。假设我们已经二分出了耗电值为 \(\text{limit}\)，我们可以枚举一下左上角和右下角的耗电值，然后判断出是否合法，再通过剩余的耗电值算出另外两个格子的耗电值是否合法即可。

代码演示

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
#include <cstdio>
#include <iostream>

int a, b, c, d;

bool check(int limit) {
    for (int i = 0; i <= std::max(std::max(a, 4 * d), std::max(2 * b, 2 * d)); i++) {
        for (int j = 0; j <= std::max(std::max(4 * a, d), std::max(2 * b, 2 * d)); j++) {
            if (i + j > limit) continue;
            if ((limit - i - j) / 2 < std::max(a - i - j / 4, d - i / 4 - j)) continue;

            int res = limit - i - j;
            int y = std::max(0, b - i / 2 - j / 2), z = std::max(0, c - i / 2 - j / 2);
            for (int k = 0; k <= res; k++) {
                if (k + (res - k) / 4 >= y && k / 4 + res - k >= z) {
                    return true;
                }
            }
        }
    }

    return false;
}

int main() {
    scanf("%d %d %d %d", &a, &b, &c, &d);

    int l = 1, r = a + b + c + d;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", l);

    return 0;
}