5289. 奶牛做題 - AcWing題庫(kù)

貝茜正在參加一場(chǎng)奶牛智力競(jìng)賽。

賽事方給每位選手發(fā)放?n?張?jiān)嚲怼?/p>

每張?jiān)嚲戆?k?道題目，編號(hào)?1～k。

已知，不同卷子上的相同編號(hào)題目的難度相同，解題時(shí)間也相同。

其中，解決第?i?道題（無(wú)論哪張?jiān)嚲?#xff09;所需的時(shí)間為?ti 分鐘。

每解決?1?道題目，就可以獲得?1?分。

因此，每張?jiān)嚲淼淖罱K得分等于這張卷子上被解決的問(wèn)題數(shù)量。

此外，每有一張滿分試卷（即成功解決卷子上全部?k?個(gè)問(wèn)題的試卷），還可以額外獲得?1?分獎(jiǎng)勵(lì)。

比賽的持續(xù)時(shí)長(zhǎng)為?M分鐘，請(qǐng)你計(jì)算貝茜最多可能獲得多少分。

輸入格式

第一行包含三個(gè)整數(shù)?n,k,M。

第二行包含?k?整數(shù)?t1,t2,…,tk。

輸出格式

一個(gè)整數(shù)，表示貝茜可能得到的最大分?jǐn)?shù)。

數(shù)據(jù)范圍

前?44?個(gè)測(cè)試點(diǎn)滿足?1≤n,k≤5
所有測(cè)試點(diǎn)滿足?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

?貪心思路：

先枚舉做多少套成套試卷。

然后按照時(shí)間從小到大做每一道題，直至剩余時(shí)間不足。

取答案最大值即

AC code：

#include<bits/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;
}