Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2017
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.83 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. #define debug true
  7. #define DBG if (debug) cout
  8.  
  9.  
  10. struct Solution {
  11. double lg_sum;
  12. int l, r; // 左右界(包含)
  13.  
  14. Solution(double lg_sum, int l, int r): lg_sum(lg_sum), l(l), r(r) {}
  15.  
  16. bool operator < (const Solution& o) const {
  17. return lg_sum < o.lg_sum; // 比較用的函數,用於讓 priority queue 排序
  18. }
  19. };
  20.  
  21. typedef struct Solution sol;
  22.  
  23. int main() {
  24. int T; // numbers of test cases
  25. scanf("%d", &T);
  26.  
  27. while (T--) { // for every test cases
  28. int N;
  29. priority_queue<sol> sols; // 連續區間組成的 pq,用於排序答案
  30. scanf("%d", &N);
  31.  
  32. sols.push(sol(0, 1, N)); // 預留一個 log 總和為零的,以免沒有答案
  33. int t, left = 0; // 暫存、目前區段的左界
  34. double cur_sum = 0; // 目前區段的 log 總和
  35.  
  36. for (int i = 0; i <= N; i++) { // 這邊是 <= 不是 <
  37. if (i != N) scanf("%d", &t);
  38. else t = 0; // 因為要包含最後面的區段,所以在這邊多計算一個(出界)
  39.  
  40. if (t && cur_sum == 0) { // 新的區段
  41. DBG << "New segment! Starting at " << i+1 << endl;
  42. cur_sum = log(t);
  43. left = i+1;
  44. } else if (t == 0 && cur_sum) { // 遇到 0 了,上一個區段結束
  45. DBG << "Closing segment: Log sum - " << cur_sum << "[" << left << ", " << i << "]\n";
  46. sols.push(sol(cur_sum, left, i)); // 把上一個區段丟到 priority queue 中
  47. cur_sum = 0, left = 0;
  48. } else if (t) {
  49. DBG << "Add item: " << i << "(Log: " << log(t) << ")\n";
  50. cur_sum += log(t);
  51. }
  52. }
  53.  
  54. sol ans = sols.top();
  55. cout << ans.l << " " << ans.r << endl;
  56. }
  57. return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement