5289. 奶牛做題 - AcWing題庫

貝茜正在參加一場奶牛智力競賽。

賽事方給每位選手發(fā)放?n?張試卷。

每張試卷包含?k?道題目，編號?1～k。

已知，不同卷子上的相同編號題目的難度相同，解題時間也相同。

其中，解決第?i?道題（無論哪張試卷）所需的時間為?ti 分鐘。

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

因此，每張試卷的最終得分等于這張卷子上被解決的問題數(shù)量。

此外，每有一張滿分試卷（即成功解決卷子上全部?k?個問題的試卷），還可以額外獲得?1?分獎勵。

比賽的持續(xù)時長為?M分鐘，請你計算貝茜最多可能獲得多少分。

輸入格式

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

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

輸出格式

一個整數(shù)，表示貝茜可能得到的最大分數(shù)。

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

前?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<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;
}