文章目录

1. 题目描述

1.1. Limit

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description

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

1.3. Input

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

对于每组数据，

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

第二行 n n n个数表示每根火柴的长度，其中火柴长度总和 ≤ 1 0 9 \le 10^9 ≤109。

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 a_i ai​，首先对所有的火柴进行求和，得到 l e n g t h = ∑ i = 1 n a i length = \sum_{i = 1}^n a_i length=∑i=1n​ai​，然后计算 l e n g t h length length 是否能被 4 整除，若不能，输出false。

若 l e n g t h length length 能被 4 整除，将所有的火柴降序排序，判断最长的火柴 max ⁡ a i \max a_i maxai​ 是否大于 l e n g t h length length，若是，输出false。

若不是，假设当前还需要的边长长度为 b u f f e r buffer buffer，对所有的火柴进行 4 次降序遍历，如果火柴长度 a i ≤ b u f f e r a_i \le buffer ai​≤buffer，则该火柴被选取， b u f f e r = b u f f e r − a i buffer = buffer - a_i buffer=buffer−ai​，并将 a i a_i ai​ 置为 0。

如果每次遍历完以后 b u f f e r buffer buffer 都为 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");
    }
}

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。