挑选货物

【编程题目 |200分】挑选货物【2021 Q1 考试题】

时间限制：C/C++ 1秒，其他语言 2秒

空间限制：C/C++262144K，其他语言524288K

64bit IO Format：%lld

本题可使用本地IDE编码，不能使用本地已有代码，无跳出限制，

编码后请点击”保存并调试“按钮进行代码提交。

■ 题目描述

2.司机小王到仓库拉货，仓库管理员已经提前将货物打包装箱，并摆成一排。

包装箱从1开始编号。各个包装箱存放的货物数组成一个集合M={M1,M2,…,Mn}。

货车一次最多运送K件货物。

为了最大化动力，小王想一次从中挑选K的整数倍件货物，再分批运输。

仓库管理员为了方便管理，要求小王必须选择连续的包装箱，如可选择1、2、3号箱，不能选2、4、6号箱。

如果运输K整数倍件货物，请帮小王计算有多少种挑选方式。

输入描述

包装箱数为N，货车一次运送货物的最大数量为K。

各个箱子存放的货物数为M1，M2，M3，…

输入为两行，格式如下：

N K

M1 M2 M3 M4 …

N和K的取值范围皆为[1,100000]

第i个包装箱存放货物的取值范围也是[1,100000]

输出描述

一行输出有多少种挑选方式，如果不存在可行的挑选方式，请输出0。

示例1  输入输出示例仅供调试，后台判题数据一般不包含示例

输入

4 1

1 2 3 4

输出

10

解释

无论怎么拿都是1的倍数，所以可以拿1个，2个，3个，4个。

示例2   输入输出示例仅供调试，后台判题数据一般不包含示例

输入

6 4

1 2 3 4 5 6

输出

3

解释

4

3,4,5

2,3,4,5,6

C++

剩余50%内容，购买单篇文章或订阅会员后查看

#include <bits/stdc++.h>

using namespace std;

const int len = 1e5 + 5;
int N, K;
int res = 0;
map<int, int> mp;
int sum[len] = {0};

int main() 
{
    int a[len] = {0};
    cin >> N >> K;
    int goods;
    for (int i = 0; i < N; i++) {
        cin >> goods;
        if (i == 0)
            sum[0] = goods % K;
        else
            sum[i] = (sum[i - 1] + goods) % K;
        mp[sum[i]]++;
    }
    ++mp[0];
    for (int i = 0; i < K; i++) {
        res += mp[i] * (mp[i] - 1) / 2;
    }
    cout << res << endl;
    return 0;
}

[/rihide]

STICK永久会员

打赏 收藏 海报 链接