j605 - 1. 程式考試

🔗 前往 ZeroJudge 原題

題目描述

題目給定 n 個程式提交紀錄，每個紀錄包含提交時間和分數。如果提交結果為嚴重錯誤，分數為 -1。目標是計算總分，計算方式為最高分減去總提交次數減去嚴重錯誤次數的兩倍，如果計算結果為負數，則總分為 0。同時，需要輸出獲得最高分的第一次提交時間。

解題思路

這題可以使用貪心演算法來解決。遍歷所有提交紀錄，追蹤目前遇到的最高分和對應的時間。同時，計算嚴重錯誤的次數和總提交次數。最後，根據公式計算總分，並輸出總分和第一次獲得最高分的時間。由於提交紀錄已經按照時間排序，因此只需要線性遍歷即可。

複雜度分析

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

程式碼

#include <bits/stdc++.h>
using namespace std;
int s,t,ms=-1,mt,x,err; 
int main(){
	int n;
	cin >> n;
	for(int i=1;i<=n;++i){
		cin >> t >> s;
		if(s==-1)err++;
		if(s>ms)ms=s,mt=t;
	}
	cout << max(0,ms-n-err*2) << " " << mt;
}