andyli

题解 CF1203B 【Equal Rectangles】
本题可用贪心解决,首先判断是否相等的边的数量均为奇数,再将$4n$条边进行排序,最后循环将最小边*最大边进行判断是...
扫描右侧二维码阅读全文
14
2019/08

题解 CF1203B 【Equal Rectangles】

本题可用贪心解决,首先判断是否相等的边的数量均为奇数,再将$4n$条边进行排序,最后循环将最小边*最大边进行判断是否都等于一个固定的数字$k$即可。
代码如下:

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 405;

int A[maxn], cnt[10005];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= (n << 2); i++)
            scanf("%d", &A[i]), cnt[A[i]]++; // 统计相同的边数量
        bool flag = true;
        for (int i = 1; i <= 10000 && flag; i++)
            if (cnt[i] & 1)
                flag = false; // 要求均为奇数
        sort(A + 1, A + (n << 2) + 1);
        int k = A[1] * A[n << 2]; // 最小数*最大数
        for (int i = 2, j = (n << 2) - 1; i < j && flag; i++, j--)
            if (A[i] * A[j] != k)
                flag = false; // 必须等于一个相同的数k
        printf("%s\n", flag ? "YES" : "NO");
    }
    return 0;
}
Last modification:November 23rd, 2019 at 11:16 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment