P1714 切蛋糕

解題思路：求連續區間不超過k的最大值。先求出前綴和，線段樹維護前綴和，在一個長度為k的區間，找到前綴和最小的，用最后的值減去這個值，得到的就是在這個區間里的最大值。如果長度不能到達k，從1尋找就可以了。

#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double lf; typedef pair<int,int>P; const int inf = 0x7f7f7f7f; const int N = 5e5+10; const ll mod = 20000311; const double PI = 3.14;int read(){char ch=getchar();int x=0,f=1;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int random(int n){return(ll)rand()*rand()%n;}int a[N]; int tree1[N<<5];void update(int rt,int left,int right,int c,int k){if(left == right){tree1[rt] = c;return;}int mid = (left+right)/2;if(k <= mid) update(2*rt,left,mid,c,k);else update(2*rt+1,mid+1,right,c,k);tree1[rt] = min(tree1[2*rt],tree1[2*rt+1]); } int query(int rt,int left,int right,int l,int r){if(left >= l && right <= r) return tree1[rt];int mid = (left+right)/2;int ret = inf;if(l <= mid) ret = min(ret,query(2*rt,left,mid,l,r));if(r > mid) ret = min(ret,query(2*rt+1,mid+1,right,l,r));return ret; }int main(){srand((unsigned)time(0));//freopen("out.txt","w",stdout);//freopen("in.txt","r",stdin);int n = read(),m = read();for(int i = 1;i <= n;i++){cin >> a[i];a[i] += a[i-1];update(1,1,n,a[i],i);}int ans = a[1];for(int i = 1;i <= n;i++){ans = max(ans,a[i]-query(1,1,n,max(i-m,1),max(i-1,1)));}cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的P1714 切蛋糕(线段树+前缀和)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。