luogu P2381 圆圆舞蹈

佚名 6年前 (2019-04-21) 随笔 1005人围观抢沙发百度已收录

模拟T3（T2找不到原题）

维护当前枚举到的区间是l到r，通过前缀和计算顺时针距离，如果超过周长的一半，l++，否则r++，同时维护答案。可证这样做不会计算任何重复的区间，且会不断向答案转移，而且时间复杂度是O(n)的

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

呆马：

#include<cstdio> #include<algorithm>
using namespace std; typedef long long ll; ll que[100010]; ll maxx(ll a,ll b) { return a>b?a:b;} int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { ll x; scanf("%lld",&x); que[i]=que[i-1]+x; } ll l=1,r=1,ans=-2120030207; while(l<=r&&r<=n) { ll len=que[r]-que[l]; if(len*2<=que[n]) r++,ans=max(ans,len); else l++,ans=maxx(que[n]-len,ans); } printf("%lld",ans); return 0; }