NSOqwq

题解 CF1473A 【Replacing Elements】

Codeforces 1473 A 题解


题目大意

给定一个长度为 $n$ 的数组,每次在数组里选三个数,将其中一个变成另外两个数的和。

问若干次操作后是否能使数组中的数都小于等于 $d$。

做法

贪心。

每次选数组里最大的那个,换成最小的两个的和。

如果最小的那两个数的和小于 $d$,可以用这两个数不断去替换其他比它们更大的数。比如 $d = 3$, 数列为 1 2 99 100 101, 每次就可以把后面的 99 100 101 换成 $1+2$,使整个数组的数都不超过 $d$。这种情况输出 YES

否则,输出 NO

代码

#include <cstdio>
#include <algorithm>
int n, d, a[100001];
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &d);
        bool flag = true;
        for (int i = 1; i <= n; i += 1) {
            scanf("%d", &a[i]);
            if (a[i] > d) flag = false;
        }
        if (flag) { // 如果所有数都已经小于d,输出YES
            printf("YES\n");
            continue;
        }
        std::sort(a + 1, a + 1 + n);
        if (a[1] + a[2] <= d) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

2021-01-24 09:06:49 in 题解