首页 > 试题广场 >

游游刷题

[编程题]游游刷题

热度指数：118 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

游游制定了一个刷题计划，她找到了 $n$ 套试卷，每套试卷的题目数量为 $a_i$ 。游游每天上午最多打开一套试卷，下午最多打开一套试卷，也可以选择不刷题而摸鱼。当游游打开一套试卷后，她就会把上面的题目全部刷完。但是游游有强迫症，她希望每天刷的题目总数均为 $k$ 的倍数。请你计算游游最多能刷多少天的题？

输入描述:

第一行输入两个正整数和。
第二行输入个正整数

输出描述:

一个整数，代表游游最多能刷题的天数。

示例1

输入

5 3
1 2 3 4 5

输出

说明

第一天上午刷1号试卷，下午刷5号试卷，总共刷6题。
第二天上午摸鱼，下午刷3号试卷，总共刷3题。
第三天上午刷4号试卷，下午刷2号试卷，总共刷6题。

示例2

输入

5 3
1 1 1 1 1

输出

说明

显然，游游没有任何一个方案可以开始刷题。

算法知识视频讲解

Handa_Rei

让a[i]对k取模，计为 $tmp=a[i]\%k$ 。如果 $tmp=0$ ，那么当天只做这一套卷子,ans++。否则（tmp!=0），如果 $k-tmp$ 在之前出现过，就匹配。ans++;
时间复杂度 $O(n)$ ，空间复杂度 $O(k)$

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int ans = 0;
    unordered_map<int, int> rd;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        tmp %= k;
        if (tmp == 0) ans++;
        else {
            if (rd.count(k - tmp)) {
                ans++;
                rd[k - tmp]--;
                if (rd[k - tmp] == 0)
                    rd.erase(k - tmp);
            }
            else
                rd[tmp]++;
        }
    }
    cout<<ans;
}

发表于 2023-09-29 23:26:59 回复(0)