社区讨论
这种做法对吗
P11963[GESP202503 六级] 环线参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mlk7m2xs
- 此快照首次捕获于
- 2026/02/13 09:29 6 天前
- 此快照最后确认于
- 2026/02/15 20:25 4 天前
是写错了还是思路就不对。
CPP#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
int a[200005<<1],s[200005<<1];
struct tree {
int l,r,mi=1e9;
} t[200005<<3];
void build(int p,int l,int r) {
t[p].l=l;
t[p].r=r;
if(l==r) {
t[p].mi=s[l];
return ;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
t[p].mi=min(t[p<<1].mi,t[p<<1|1].mi);
}
int query(int p,int l,int r) {
if(l<=t[p].l&&t[p].r<=r) {
return t[p].mi;
}
int mid=t[p].l+t[p].r>>1,res=INT_MAX;
if(l<=mid)res=min(res,query(p<<1,l,r));
if(r>mid)res=min(res,query(p<<1|1,l,r));
return res;
}
signed main() {
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
s[i]=s[i-1]+a[i];
}
for(int i=1; i<=n; i++) {
a[n+i]=a[i];
s[n+i]=s[n+i-1]+a[n+i];
}
build(1,1,n<<1);
for(int i=1; i<=(n<<1); i++) {
ans=max(ans,s[i]-query(1,max(1ll,i-n+1),i));
}
cout<<ans;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...