i959 - 11078 - Open Credit System

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算高年級學生比任何低年級學生獲得的最高分數差。給定一個整數陣列，其中索引較小的學生年級較高，需要找到對於每個高年級學生，其分數與後續所有低年級學生的最高分數之間的差的最大值。

解題思路

這題可以使用貪心策略解決。我們遍歷學生分數陣列，維護一個變數 ma 記錄目前遇到的最高分數。對於每個學生，計算 ma 減去該學生的分數，並將結果與目前的答案 ans 進行比較，更新 ans。同時，更新 ma 為目前遇到的最高分數。由於題目保證 i < j 表示第 i 個學生年級比第 j 個學生大，因此可以保證計算的差值是高年級學生與低年級學生的分數差。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	int t,n,x,ans,ma;
	for(cin >> t;t--;cout << ans << "\n"){
		ans=-1e9,ma=-1e9;
		for(cin >> n;n--;){
			cin >> x;
			ans=max(ma-x,ans);
			ma=max(ma,x);
		}
	}
}