5289. 奶牛做题 - AcWing题库

贝茜正在参加一场奶牛智力竞赛。

赛事方给每位选手发放 n 张试卷。

每张试卷包含 k 道题目，编号 1∼k。

已知，不同卷子上的相同编号题目的难度相同，解题时间也相同。

其中，解决第 i 道题（无论哪张试卷）所需的时间为 ti 分钟。

每解决 1 道题目，就可以获得 1 分。

因此，每张试卷的最终得分等于这张卷子上被解决的问题数量。

此外，每有一张满分试卷（即成功解决卷子上全部 k 个问题的试卷），还可以额外获得 1 分奖励。

比赛的持续时长为 M分钟，请你计算贝茜最多可能获得多少分。

输入格式

第一行包含三个整数 n,k,M。

第二行包含 k 整数 t1,t2,…,tk。

输出格式

一个整数，表示贝茜可能得到的最大分数。

数据范围

前 44 个测试点满足 1≤n,k≤5 所有测试点满足 1≤n,k≤45，0≤M≤2×109，1≤ti≤106。

输入样例1：

3 4 11

1 2 3 4

输出样例1：

6

输入样例2：

5 5 10

1 2 4 8 16

输出样例2：

7

贪心思路：

先枚举做多少套成套试卷。

然后按照时间从小到大做每一道题，直至剩余时间不足。

取答案最大值即

AC code：

#include

using namespace std;

int n, k, m;

int arr[50];

int sum = 0;

int main() {

cin >> n >> k >> m;

for (int i = 1; i <= k; i++) {

cin >> arr[i];

sum = sum + arr[i];

}

sort(arr + 1, arr + k + 1);

int ans = 0;

for (int i = 0; i <= n; i++) {

int time = sum * i;

if (time > m) break;

int x = m - time;

int res = i * k + i;

for (int j = 1; j <= k; j++) {

if (x < arr[j]) break;

int num = min(n - i, x / arr[j]);

res += num;

x -= num * arr[j];

}

ans = max(ans, res);

}

cout << ans;

}