【Smart - Ⅰ】C 布置停车场

Blikewsr · 2022-08-15 11:10:16 · 题解

• \color{grey}\text{[C 布置停车场 原题链接]}

  • 题目描述
    由于疫情， 停车场上任何两辆车不得相邻。这里相邻指车位含有 公共点， 要求最少要封禁多少个车位能满足每辆汽车都不相邻。

  • 输入格式
    第一行，一个整数 T，表示数据组数。
    接下来 T 行：两个整数 n 和 m 。

  • 输出格式
    输出一个整数，由空格隔开。表示最少封禁的车位数量。

  • 思路
    首先， 根据题目， 我们可以知道题目要我们求最少封禁停车位数量。

  那么， 我们其实可以先求出最多还剩余多少个停车位， 然后再用总车位数减去最多剩余车位数就可以了。

  接着， 我们可以现拿几个 n = m 的数据暴力求一下解（至于为什么用 n = m 的数据， 纯粹是因为更好画图）。

  所以， 最大剩余车位数就等于一排拥有的车位数乘上一列拥有的车位数。

  所以， 一排拥有的车位数和一列拥有的车位数就等于该排或该列的总车位数除以 2。

  但是， 如果该排或该列的总车位数是奇数， 那么一排拥有的车位数和一列拥有的车位数就会有问题， 所以我们可以将他们向上取整。

  那么， 根据这些， 我们很容易推出一个公式（n = m 的情况下）。

  但是， 这个是只针对于 n = m 的情况的， 但还有一些 n != m 的情况， 那么， 我们可以带进去试试。

  看看样例， 嗯， 挺好的， 全 WA， 啊不， 全 AC。

  所以， 这道题目就可以用这个公式过掉。

  注意， 在做除法是要向上取整。

  • 代码

    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    int T;
    signed main() {
    cin >> T;
    while (T --) {
    int n, m;
    cin >> n >> m;
    cout << n * m - ceil(n * 1.0 / 2.0) * ceil(m * 1.0 / 2.0) << '\n';
    }
    return 0;
    }

  • 此题解仅供参考， 欢迎指正， 谢谢！