与其思考 是先尽可能做完所有的低时间题目得分最多还是尽可能按一整套试卷做得分多,不如枚举自己思考的各种可能。
当i=0时,就是试验“先尽可能做完所有的低时间题目”
当i=其他值时,就是尝试 我做完一整套,两整套…,然后做尽量多的其它低时间的题目(贪心),就求得了最多得分。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50;
int n,k,m;
int w[N];
int main()
{
scanf("%d%d%d", &n,&k,&m);
//记录 完成一套试卷的时间
int sum = 0;
for(int i = 0; i < k; i++){
scanf("%d", &w[i]);
sum += w[i];
}
sort(w,w+k);
int res = 0;
//先计算如果 完成一整套试卷的时间,遍历i从0到n,表示完成了0,1,2..n套试卷
for(int i = 0; i<= n;i ++){
int cost = i*sum;
if(cost>m) break;
int score = (k+1)*i; // 完成了i整套 的得分
for(int j = 0; j < k; j++){
int t = w[j]*(n-i); // 计算 在完成了i整套试卷后, 剩余的n-i套试卷中的j题,就从按照代价从小到大的依次完成
if(cost+t <= m){ // 做完了 剩余的n-i套试卷中的j题还有剩余的时间
cost += t; // 更新当前的代价
score += (n-i); //更新分数
}else{ // 不能完成剩余的n-i套试卷中 所有的j题, 剩下的时间只能完成部分j了
int x = (m-cost)/w[j]; // 计算剩下的时间 还能完成几道j题
score += x;
cost += (x*w[j]);
}
}
res = max(score,res);
}
printf("%d\n", res);
return 0;
}