c318 - rilak的期末考 前傳
題目描述
題目描述了 rilak 在準備期末考時，面對多個章節和有限時間的情況下，如何最大化考試得分的問題。每個章節讀取多次，得分會遞減，且每次遞減的幅度固定。目標是找到最佳的讀取策略，使得在時間限制內獲得的總分最高。
解題思路
此題採用貪心策略。每次都選擇目前可以獲得最高分數的章節進行讀取。具體來說，每次迭代都找出所有章節中當前可獲得分數的最大值，然後讀取該章節，並更新該章節的剩餘可讀取次數和分數。這個過程重複進行，直到時間耗盡。
複雜度分析
- 時間複雜度: O(N*T)
- 空間複雜度: O(N)
程式碼
#include <iostream>
using namespace std;
int main(){
int n,t,ans=0;
cin >> n >> t;
int a[n][2],mn;
for(int i=0;i<n;++i)
cin >> a[i][0] >> a[i][1];
while(t--){
mn=0;
for(int i=0;i<n;++i)
mn=max(a[i][0],mn);
for(int i=0;i<n;++i){
if(a[i][0]==mn){
ans+=a[i][0];
a[i][0]-=a[i][1];
a[i][0]=max(0,a[i][0]);
break;
}
}
}
cout << ans;
}