NSOqwq

题解 CF1476A 【K-divisible Sum】

Educational Codeforces Round #103 A 题解

题目大意

尝试构造出一个长度为 $n$ 的正整数数列,使它各个数和能被 $k$ 整除,并使这个数列里的最大数尽可能的。输出这个最小值。

做法

贪心。

1. 这个数列的总和肯定是越小越好。

这个是显而易见的,因为如果数列的总和大,数列中的最大数也会大。

所以,要求的这个数列的总和是最小的不小于 $n$ 的 $k$ 的倍数
(因为要求的是正整数数列,所以它的总和一定大于等于 $1 \times n = n$)

这个数用代数式表示出来即为 $\lceil \dfrac n k \rceil \times k$。

(不要用循环查找这个数,会超时)

2. 数组中数值的分配一定是尽量平均。

比如数组总和为 $10$,要分成 $3$ 个数的和,一定是分成 $(3, 3, 4)$ (尽量平均),而不是 $(1, 2, 7), (2, 3, 5)$ 这种分配方式。这样,数组中的最大数才会最小。

发现如果平均分配的话,数组中最大数即为 $\lceil \dfrac {sum} n \rceil$。

代码

#include <cstdio>
int t;
int main() {
    scanf("%d", &t);
    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);

        int c = n / k;
        if (n % k != 0)
            c += 1; // 找 ceil(n / k)
        int sum = k * c; // ceil(n / k) * k 即为数组的总和

        if (sum % n == 0)
            printf("%d\n", sum / n);
        else
            printf("%d\n", sum / n + 1);
        // ceil(sum / n) 就是答案
    }
    return 0;
}

2021-02-01 08:26:03 in 题解