k466 - 成績分析 (Analysis)

🔗 前往 ZeroJudge 原題

題目描述

題目給定一系列學生的成績，要求計算最高可能的學號和最低可能的學號。學號的計算方式比較特殊，需要根據學生的成績變化進行模擬。

解題思路

這題的核心在於模擬學號的產生規則。學號的產生受到學生成績的影響，如果後一個學生的成績比前一個高，則學號增加 (成績差 * 1001)；如果後一個學生的成績比前一個低，則學號減少 (成績差 * m)。 題目要求計算所有可能的學號中，最大的學號模 1001 和最小的學號模 1001。 程式碼使用迴圈模擬學生的成績變化，並在每次變化時更新學號。ma 記錄目前找到的最大學號，mi 記錄目前找到的最小學號。由於學號可能很大，因此在計算最大和最小學號時，都取模 1001。

複雜度分析

• 時間複雜度: O(n)，其中 n 是學生的數量。程式碼需要遍歷所有學生的成績。
• 空間複雜度: O(1)。程式碼只使用了幾個變數來記錄學號和成績，空間複雜度是常數級別。

程式碼

#include <iostream>
using namespace std;
int m,x,ma=-1,mi=-1,l,up,d;
int main(){
	cin >> m >> m;
	for(up=1;cin >> l;++up){
		up%=1001;
		d=1;
		for(d%m==1;d%m!=0;++d){
			cin >> x;
			if(x>l){
				up+=(x-l)*1001;
			}
			else{
				d+=(l-x)*m;
			}
			l=x;
		}
		d/=m;
		if(up>ma+1000)
			ma=up;
		if(d*1001>mi)
			mi=d*1001+up%1001;
	}
	cout << ma%1001 << "\n" << mi%1001;
}