Skip to content

51Nod 3063 小明爱正方形#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description#

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

1.3. Input#

第一行一个数，表示数据的组数；

对于每组数据，

第一行输入一个数，表示火柴的数目，其中 ；

第二行个数表示每根火柴的长度，其中火柴长度总和 。

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. 解读#

设火柴长度为 ，首先对所有的火柴进行求和，得到 ，然后计算 是否能被 4 整除，若不能，输出false。

若 能被 4 整除，将所有的火柴降序排序，判断最长的火柴 是否大于 ，若是，输出false。

若不是，假设当前还需要的边长长度为 ，对所有的火柴进行 4 次降序遍历，如果火柴长度 ，则该火柴被选取，，并将 置为 0。

如果每次遍历完以后 都为 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，有问题欢迎通过邮箱交流。

Back to top