題目敘述
輸入說明
輸入的第一列包含兩個正整數 $N, M$ ($1\le N\le 100000; 1\le M\le 10^9$)依序代表題目的數量與比賽的時間長度。第二列包含 $N$ 個整數 $A_i$($1\le A_i\le 10^9$),第三列包含 $N$ 個整數 $B_i$($1\le B_i\le 10^9$)。
輸出說明
如果不存在任何方法使得 Ayu 最終題數嚴格大於 Budi 的題數,輸出 -1
。否則的話輸出一個整數 $K$,然後在第二列輸出 $K$ 個嚴格遞增的數字:Ayu 只要在這些時間點戳破氣球,就可以贏過 Budi。
範例輸入 1
4 30
9 10 10 10
4 10 5 10
範例輸出 1
2
12 19
範例輸入 2
5 50
10 10 10 10 10
15 12 19 17 20
範例輸出 2
0
範例輸入 3
5 10
15 10 5 5 5
9 10 10 10 10
範例輸出 3
-1
OJ 連結
解法
俗話說得好:氣球恆久遠,一顆永流傳。如果 Ayu 在 Budi 解題目解到一半的時候戳破氣球嚇嚇他,倒不如多等一下,在 Budi 即將解出來的那剎那說時遲那時快再把氣球戳破,讓 Budi 重來感覺豈不是更好嗎!
假設我們有個答案,那我們可以把 Budi 的解題心路歷程記錄下來,比方說(紅色的字代表被嚇到所以沒有解出該題):
$$ B_1, B_2, \red{B_3}, \red{B_3}, B_3, \red{B_4}, B_4, B_5, ... $$
如果今天 $B_3 < B_4$,那麼 Ayu 總是可以再多等一下,讓 Budi 重做 $B_4$ 總是比重做 $B_3$ 賺更多!
以上的觀察引導我們使用「堆疊」的解法,去模擬 Ayu 的選擇,把得到的氣球花在 Budi 的哪些題目上頭。我們維護一個堆疊,從堆疊底部到頂部,永遠是「任務編號遞增、所花費時間嚴格遞減」並且紀錄有多少顆氣球花在這題上面。
以下面這個例子而言,假設 Ayu 可以在以 下時間 8, 20, 40, 48, 56, 65, 109, 114, 117, 118 分別獲得氣球,那堆疊的改變看起來會像這樣:
如果總比賽時間 $M=119$,那麼 Ayu 能讓 Budi 在第 119 分鐘的時候還做不出最後一題,因此 Ayu 能夠獲勝。
參考程式碼
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N, M;
cin.sync_with_stdio(false);
cin >> N >> M;
vector<long long> A(N), B(N);
for (int i = 0; i < N; i++) cin >> A[i];
for (int i = 0; i < N; i++) cin >> B[i];
// 先算出 Ayu 拿到每顆氣球的時間點,並算出 Ayu 可以解幾題。
int nsolved = 0;
for (int i = 1; i < N; i++) A[i] += A[i - 1];
for (int i = 0; i < N; i++) nsolved += (A[i] <= M);
// 我們目標就是要讓 Budi 解出第 nsolved 的時間嚴格大於 M。
long long t = 0;
vector<pair<int, int>> stack;
for (int i = 0, j = 0; i < nsolved; i++) {
int balloons = 0;
while (!stack.empty() && B[stack.back().first] <= B[i]) {
balloons += stack.back().second;
t -= stack.back().second * B[stack.back().first];
stack.pop_back();
}
t += B[i] * (balloons + 1);
while (j < nsolved && A[j] <= t) {
++j;
++balloons;
t += B[i];
}
stack.push_back(make_pair(i, balloons));
}
// 如果還是在 M 分鐘內解出來了,就輸出 -1。
if (t <= M) {
cout << "-1" << endl;
return 0;
}
// 計算每顆氣球被戳破的時間。
t = 0;
int j = 0;
vector<long long> ans;
for (auto [i, b] : stack) {
while (j < i) t += B[j++];
for (int l = 0; l < b; l++)
ans.push_back(t += B[i]);
}
// 輸出答案。
while (!ans.empty() && ans.back() > M) ans.pop_back();
cout << ans.size() << endl;
for (auto x : ans) cout << x << " ";
cout << endl;
return 0;
}
關於競程日記
🍅 如果您想到更多有趣漂亮簡單乾淨的解法話歡迎留言給競程日記小編群!
ℹ️ 這是一篇投稿給競程日記的文章,歡迎大家投稿、交流與分享程式解題競賽的點點滴滴!