地图网站设计,网站开发模式框架,wordpress主题 视频,小波app推广网5289. 奶牛做题 - AcWing题库 贝茜正在参加一场奶牛智力竞赛。 赛事方给每位选手发放 n 张试卷。 每张试卷包含 k 道题目#xff0c;编号 1∼k。 已知#xff0c;不同卷子上的相同编号题目的难度相同#xff0c;解题时间也相同。 其中#xff0c;解决第 i 道题#xff08;…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≤450≤M≤2×1091≤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 #includebits/stdc.h
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;
}
