長度不超過n的連續最大和___優先隊列

題目鏈接:

https://nanti.jisuanke.com/t/36116

題目:

在蒜廠年會上有一個抽獎，在一個環形的桌子上，有?nn?個紙團，每個紙團上寫一個數字，表示你可以獲得多少蒜幣。但是這個游戲比較坑，里面竟然有負數，表示你要支付多少蒜幣。因為這些數字都是可見的，所以大家都是不會出現的賠的情況。

游戲規則：每人只能抓一次，只能抓取一段連續的紙團，所有紙團上的數字和就是你可以獲得的蒜幣。

蒜頭君作為蒜廠的一員在想，我怎么可以獲得最多的蒜幣呢？最多能獲取多少蒜幣呢？

因為年會是發獎，那么一定有大于?00?的紙團。

輸入格式

第一行輸入一個整數?nn，表示有?nn?個紙團。

第二行輸入輸入?nn?個整數?a_iai?，表示每個紙團上面寫的數字（這些紙團的輸入順序就是環形桌上紙團的擺放順序）。

輸出格式

輸出一個整數，表示蒜頭君最多能獲取多少蒜幣。

數據范圍

對于?30\%30%?的數據：1 \le n \le 10^2,-10^3 \le a_i \le 10^31≤n≤102,?103≤ai?≤103。

對于?60\%60%?的數據：1 \le n \le 5 \times 10^3,-10^6 \le a_i \le 10^61≤n≤5×103,?106≤ai?≤106。

對于?100\%100%?的數據：1 \le n \le 10^5,-10^9 \le a_i \le 10^91≤n≤105,?109≤ai?≤109。

樣例輸入

?3

1 -2 1

樣例輸出

2

題目來源

2019 藍橋杯省賽 B 組模擬賽（一）

?

?

分析: 求循環的連續最大和.

? ?循環好解決:? ?把數組首尾連成2n長的.

? 然后就是求長度不超過n的最大連續和.

? 一般求連續和 直接用前綴和,然后逐步做差即可.

?但是這兒有個限制,要求長度不超過n. 所以我們可以用優先隊列:

? 維護一個結構體?

?struct node {

　　ll val;

? ? ? ?int index;

};

?根據index判斷一下長度是否超過n即可.

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5+50;ll arr[maxn * 2];struct node {ll val;int index;bool operator < (const node &a) const {if (val != a.val) return val > a.val;return index > a.index;}node () {}node (ll vv, int ii) : val(vv), index(ii) {}
};int main() {ios::sync_with_stdio(false);int n;cin >> n;for (int i=0; i<n; ++i)cin >> arr[i];for (int i=n; i<2*n; ++i)arr[i] = arr[i-n];for (int i=1; i<2*n; ++i)arr[i] = arr[i] + arr[i-1];ll res = -8626213631111ll;ll tans;priority_queue<node> pq;for (int i=0; i<2 * n; ++i) {if (pq.empty()) tans = arr[i];if (tans > res) res = tans;while (!pq.empty()) {node tmp = pq.top();if (i - tmp.index >= n) {pq.pop();continue;} else {tans = arr[i] - tmp.val;break;}}if (tans > res) res = tans;pq.push({arr[i], i});}cout << res << endl;return 0;
}

?