【題解】UVA-11078 Open Credit System

【題目敘述】https://vjudge.net/problem/UVA-11078 (考生答對率: 12.77%)
【解題想法】依題意 2 <= n <= 100,000,須避免重複的計算,否則會TLE。使用兩個set(st1 和 st2),st1 紀錄已經出現過的學生成績,*st1.rbegin() 的值即為目前為止最高分數。當有新同學加入時(分數 x),只要計算 (*st1.rbegin()) – x 的值,即為新同學與所有老同學的分數差距最大值。再把這個分數差距值紀錄於 st2,最後 *st2.rbegin() 即為答案。

#include <iostream>
#include <set>
using namespace std;
int T, n, x;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> n;
        set <int> st1, st2;
        cin >> x;
        st1.insert(x); //senior
        for (int i = 1; i < n; i++) {
            cin >> x;
            st2.insert((*st1.rbegin()) - x); //max(senior - junior)
            st1.insert(x);
        }
        cout << *st2.rbegin() << "\n";
    }
    return 0;
}
分享本文 Share with friends