51Nod 3063 小明爱正方形简单题

文章目录

1. 题目描述
2. 解读
3. 代码

1. 题目描述

1.1. Limit

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description

小明很喜欢正方形，也喜欢火柴，现在小明有一些火柴，现在小明想知道用所有的火柴棒能不能拼成一个正方形。

1.3. Input

第一行一个数 $T$ ，表示数据的组数 $(1 \leq T \leq 10)$ ；

对于每组数据，

第一行输入一个数 $n$ ，表示火柴的数目，其中 $1 \leq n \leq 15$ ；

第二行 $n$ 个数表示每根火柴的长度，其中火柴长度总和 $\leq 1 0^{9}$ 。

1.4. Output

对于每组数据输出一行，如果所有的火柴可以拼成正方形，输出true，否者输出false。

1.5. Sample Input

1
5
1 1 2 2 2

1.6. Sample Output

true

1.7. Source

51Nod 3063 小明爱正方形

2. 解读

设火柴长度为 $a_{i}$ ，首先对所有的火柴进行求和，得到 $l e n g t h = \sum_{i = 1}^{n} a_{i}$ ，然后计算 $l e n g t h$ 是否能被 4 整除，若不能，输出false。

若 $l e n g t h$ 能被 4 整除，将所有的火柴降序排序，判断最长的火柴 $\max a_{i}$ 是否大于 $l e n g t h$ ，若是，输出false。

若不是，假设当前还需要的边长长度为 $b u f f e r$ ，对所有的火柴进行 4 次降序遍历，如果火柴长度 $a_{i} \leq b u f f e r$ ，则该火柴被选取， $b u f f e r = b u f f e r - a_{i}$ ，并将 $a_{i}$ 置为 0。

如果每次遍历完以后 $b u f f e r$ 都为 0，即4条边都被火柴拼凑出来了，则输出true，否则输出false。

3. 代码

#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;

const int NUM = 15;
// 存储
long long list[NUM];
// 定义降序排序规则
bool cmp(long long a, long long b)
{
    return a > b;
}

int main()
{
    // test case
    int t, n;
    scanf("%d", &t);
    // sum 存储所有火柴的求和
    long long sum;
    // flag 存储结果
    bool flag;
    // buffer
    long long buffer, inputBuffer;
    // length 存储正方形4条边的长度
    long long length;
    // 输入
    for (int i = 0; i < t; i++) {
        // 初始化
        memset(list, 0, sizeof(list));
        sum = 0;
        flag = true;
        // 输入
        scanf("%d", &n);
        for (int j = 0; j < n; j++) {
            scanf("%lld", &inputBuffer);
            list[j] = inputBuffer;
            // 累加
            sum += inputBuffer;
        }
        // 降序排序
        sort(list, list + n, cmp);
        // 计算
        // 若不能分为4条边
        if (sum % 4 != 0 || list[0] > sum / 4) {
            flag = false;
        } else {
            // 若能够分为4条边
            // 计算每条边的长度
            length = sum / 4;
            for (int j = 0; j < 4; j++) {
                // 用buffer存储需要的长度
                buffer = length;
                for (int k = 0; k < n; k++) {
                    // 若需要的长度大于火柴长度
                    if (buffer >= list[k]) {
                        // 选择该根火柴
                        buffer -= list[k];
                        // 长度置为0
                        list[k] = 0;
                        // 若需要的长度为0时则退出循环
                        if (buffer == 0) {
                            break;
                        }
                    }
                }
                // 若不能用火柴凑出需要的边长
                if (buffer > 0) {
                    flag = false;
                    break;
                }
            }
        }
        // 输出
        printf("%s\n", flag ? "true" : "false");
    }
}