Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <cmath>
- using namespace std;
- #define debug true
- #define DBG if (debug) cout
- struct Solution {
- double lg_sum;
- int l, r; // 左右界(包含)
- Solution(double lg_sum, int l, int r): lg_sum(lg_sum), l(l), r(r) {}
- bool operator < (const Solution& o) const {
- return lg_sum < o.lg_sum; // 比較用的函數,用於讓 priority queue 排序
- }
- };
- typedef struct Solution sol;
- int main() {
- int T; // numbers of test cases
- scanf("%d", &T);
- while (T--) { // for every test cases
- int N;
- priority_queue<sol> sols; // 連續區間組成的 pq,用於排序答案
- scanf("%d", &N);
- sols.push(sol(0, 1, N)); // 預留一個 log 總和為零的,以免沒有答案
- int t, left = 0; // 暫存、目前區段的左界
- double cur_sum = 0; // 目前區段的 log 總和
- for (int i = 0; i <= N; i++) { // 這邊是 <= 不是 <
- if (i != N) scanf("%d", &t);
- else t = 0; // 因為要包含最後面的區段,所以在這邊多計算一個(出界)
- if (t && cur_sum == 0) { // 新的區段
- DBG << "New segment! Starting at " << i+1 << endl;
- cur_sum = log(t);
- left = i+1;
- } else if (t == 0 && cur_sum) { // 遇到 0 了,上一個區段結束
- DBG << "Closing segment: Log sum - " << cur_sum << "[" << left << ", " << i << "]\n";
- sols.push(sol(cur_sum, left, i)); // 把上一個區段丟到 priority queue 中
- cur_sum = 0, left = 0;
- } else if (t) {
- DBG << "Add item: " << i << "(Log: " << log(t) << ")\n";
- cur_sum += log(t);
- }
- }
- sol ans = sols.top();
- cout << ans.l << " " << ans.r << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement