社区讨论

这种做法对吗

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 条回复,欢迎继续交流。

正在加载回复...