2222 年 5 月,大廠牌電子機械製造商 ARGUS 發佈了能夠實現虛擬實境的機器 NerveGear,人們可以通過 NerveGear 進行完全潛行以進入虛擬世界。不久,全球首款虛擬實境大型多人線上角色扮演遊戲《刀劍神域》在經過大約一千人參加的封閉測試後正式發佈,首次共限量發售一萬份。《刀劍神域》於 2222 年 11 月 6 日下午 1 時正式開始營運。
明奕身為《刀劍神域》的粉絲,他當然不只是搶到了封閉測試的資格,也拿到了限量的正式版參與名額,並在遊戲營運當天馬上登入了遊戲。而你,身為明奕的朋友,雖然沒有搶到正式版名額,但也非常關注《刀劍神域》的消息。在遊戲開始營運後沒多久,還在蒐集資訊的你便發現了遊戲設計者茅場晶彥的陰謀──《刀劍神域》將會在時間 $T$ 之後關閉登出指令,並成為一個不破關就無法登出、在遊戲內死去也會在現實中死去的死亡遊戲!
但這時你回想起來,明奕曾經說過他只打算在第一天把遊戲角色升級到 $L$ 等就先退出遊戲去趕他的計安作業,所以只要明奕成功在時間 $T$ 以前練到 $L$ 等,他就可以平安無事的提早度過這個風波。在你確認過手邊整理過的遊戲資料後,你發現這個遊戲目前有 $N$ 個任務可以接,每個任務有兩個參數 $l_i, t_i$,代表可以接下這個任務的最低等級和所需花費的時間,並且在一開始時,所有玩家的等級都是 $1$ 等,在《刀劍神域》裡升到 $L$ 等之前,每一等都只需要完成 $K$ 個任務就可以升一等。
你知道明奕一定會用最少的時間升到 $L$ 等,但你一時又聯絡不上專心練等的明奕,因此你只好先計算出他升到 $L$ 等的最少時間,並根據他能不能在時間 $T$ 以前升到 $L$ 等來採取下一步的動作,快撰寫一支程式來完成這件事情吧!
以下為提供的解法,但是卻得到 WA,請在 edit distance $8$ 以內將該程式碼修改正確:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int N, L, K, T;
string s = "Impossible";
cin >> N >> L >> K >> T;
vector<pair<int, int>> arr(N);
for (auto &[l, t] : arr)
cin >> l >> t;
sort(arr.begin(), arr.end(), [](pair<int, int> a, pair<int, int> b) {
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
});
auto quited = [&](string &verdict) {
int ans = 0, lv = 1;
priority_queue<int, vector<int>, greater<int>> min_heap;
for (int pt = 0, exp = 0; lv < L;) {
while (pt < N && arr[pt].first <= lv)
min_heap.push(arr[pt++].second);
if (min_heap.empty()) return verdict;
ans += min_heap.top();
min_heap.pop();
exp += 1;
if (exp == K) exp = 0, lv += 1;
}
if (ans > T)
verdict = "Time Limit Exceeded";
else {
cout << ans << "\n";
exit(0);
}
return verdict;
};
cout << quited(s) << "\n";
}
輸入首行有四個整數 $N, L, K, T$,代表任務的數量、明奕的目標等級、升一等所需完成的任務數量和《刀劍神域》關閉登出指令的時間點。
接下來 $N$ 行,第 $i$ 行兩個整數 $l_i, t_i$,代表接下第 $i$ 個任務的最低等級限制、以及完成第 $i$ 個任務所需花費的時間。
如果明奕其實不能靠當前這 $N$ 個任務升到 $L$ 等,輸出 "Impossible"(含引號)於一行,否則,假設明奕升到 $L$ 等的最少時間為 $x$,若 $x > T$,表示明奕已經來不及退出遊戲了,輸出 "Time Limit Exceeded"(含引號)於一行;反之輸出 $x$ 於一行。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資。 | 0 |
2 | 0~8 | 無特別限制。 | 50 |