f174 - m6a2-蛋糕(Cake)

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出一個長度不超過 K 的連續蛋糕區塊，使得該區塊的總喜好度分數最大。如果所有區塊的分數都小於 0，則輸出 0。

解題思路

本題可以使用前綴和和單調隊列來優化求解。首先，計算前綴和，以便快速計算任意區間的總和。然後，使用單調隊列來維護一個窗口，窗口大小為 K。單調隊列中存儲的是前綴和的負值，以及對應的索引。這樣，在滑動窗口的過程中，可以快速找到當前窗口中最大的前綴和（即最小的負值）。

具體來說，對於每個位置 i，首先將窗口左邊超出 K 的元素從單調隊列中移除。然後，將當前位置 i 的前綴和的負值加入單調隊列中。在加入之前，需要將單調隊列中比當前值小的元素移除，以保持單調性。最後，計算當前窗口的最大總和，即當前前綴和加上單調隊列中的最大值（即最小的負值）。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(k)

程式碼

#include <bits/stdc++.h>
using namespace std;
int n,k,ans,x,tmp;
priority_queue <pair <int,int>> pq;//v it;
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> n >> k;
	pq.push({0,0});
	for(int i=1;i<=n;++i){
		cin >> x;
		tmp+=x;
		while(!pq.empty()&&i-pq.top().second>k)pq.pop();
		ans=max(ans,tmp+pq.top().first);
		pq.push({-tmp,i});
	}
	cout << ans;
}