andyli

题解 CF1133B 【Preparation for International Women's Day】
题目要求$k|d_i+d_j$,可以理解为$d_i\%k+d_j\%k=0 \texttt{或} k$,所以先将输...
扫描右侧二维码阅读全文
13
2019/08

题解 CF1133B 【Preparation for International Women's Day】

题目要求$k|d_i+d_j$,可以理解为$d_i\%k+d_j\%k=0 \texttt{或} k$,所以先将输入的序列$d$按除以$k$的余数进行分类,假设$cnt[i]$表示输入序列中$\%k=i$ 的数量,那么礼物的个数就是$\frac{cnt[0]}{2}+\{min(cnt[i],cnt[j]) | i <j\}$,当$k$为偶数时,那么礼物个数还要加上$\frac{cnt[\frac{k}{2}]}{2}$,最终答案的箱子数就是礼物个数$\times 2$。
代码如下:

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

int cnt[maxn];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        cnt[x % k]++; // 统计除以k余数的个数
    }
    int ans = cnt[0] / 2; // %k=0时,可以配对%k=0数量/2个礼物
    for (int i = 1, j = k - 1; i <= j; i++, j--)
        if (i == j) // k为偶数时的特殊情况
            ans += cnt[i] / 2;
        else
            ans += min(cnt[i], cnt[j]);
    printf("%d\n", ans * 2); // 箱子数=礼物数*2
    return 0;
}
Last modification:November 6th, 2019 at 05:12 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment