當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

计蒜客 A2232.程序设计：蒜厂年会-单调队列(双端队列(STL deque)实现)滑窗维护最小前缀和...

發(fā)布時間：2023/12/20 编程问答 33 豆豆

生活随笔收集整理的這篇文章主要介紹了计蒜客 A2232.程序设计：蒜厂年会-单调队列(双端队列(STL deque)实现)滑窗维护最小前缀和... 小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

程序設計：蒜廠年會問答問題反饋只看題面

?16.79%
?1000ms
?262144K

在蒜廠年會上有一個抽獎，在一個環(huán)形的桌子上，有?

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

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

因為年會是發(fā)獎，那么一定有大于?

輸入格式

第一行輸入一個整數(shù)?

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

輸出格式

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

數(shù)據(jù)范圍

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

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

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

樣例輸入復制

3 1 -2 1

樣例輸出復制

題目來源

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

因為是環(huán)形的，所以前綴和算2倍長的。、

因為是連續(xù)的，所以直接遍歷的時候，當前的前綴和-當前區(qū)間的最小的前綴和，就是最大的前綴和，單調(diào)隊列滑窗實現(xiàn)，因為總長是固定的，但是我寫了2倍長，所以要長度<=n，就沒了。

思路隊友想的。我是水的，我代碼實現(xiàn)的時候，被懟的有點難過，哈哈，太菜了。

代碼:

1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=2*1e5+10; 5 const int inf=0x3f3f3f3f; 6 7 int a[maxn]; 8 ll pre[maxn],Min[maxn]; 9 deque<ll> deq; 10 11 int main() 12 { 13 int n; 14 scanf("%d",&n); 15 for(int i=1;i<=n;i++){ 16 scanf("%d",&a[i]); 17 pre[i]=pre[i-1]+a[i]; 18 } 19 for(int i=n+1;i<=2*n;i++){ 20 pre[i]=pre[i-1]+a[i-n]; 21 } 22 deq.push_back(1); 23 ll ans=0; 24 for(int i=2;i<=2*n;i++){ 25 while(i-deq.front()>n) deq.pop_front(); 26 ans=max(ans,pre[i]-pre[deq.front()]); 27 while(deq.size()&&pre[deq.back()]>=pre[i]) 28 deq.pop_back(); 29 deq.push_back(i); 30 } 31 cout<<ans<<endl; 32 }

轉載于:https://www.cnblogs.com/ZERO-/p/10631464.html

總結

以上是生活随笔為你收集整理的计蒜客 A2232.程序设计：蒜厂年会-单调队列(双端队列(STL deque)实现)滑窗维护最小前缀和...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。