哈哈哈哈哈哈哈哈哈哈哈

啊啊啊啊啊啊啊啊啊啊啊

#include <cstdio>

int main()
{
int n;
scanf("%d",&n);
static int A[1000000];
long long AA=0;
for(int i=0;i<n;i++){
scanf("%d",A+i);
AA+=A[i];
}
long long l=0,r=AA+1;
while(l+1<r){
long long m=(l+r)/2;
static long long S[1000000];
static int P[1000000];
for(int i=0;i<n;i++){
if(i>0){
P[i]=P[i-1]-1;
S[i]=S[i-1]-A[i-1];
}
else{
P[i]=0;
S[i]=0;
}
while(S[i]<m){
S[i]+=A[(i+P[i])%n];
P[i]++;
}
}
bool B=0;
for(int i=0;i<n;i++){
if(AA-S[i]-S[(i+P[i])%n]>=m){
B=1;
}
}
if(B){
l=m;
}
else{
r=m;
}
}
printf("%lld\n",l);
return 0;
}

太简单不管了……我的口述题解应该已经够了…………

应该是二分答案+贪心，在贪心的时候注意起点变化后移动后面的两个点就行了

#include <cstdio>

int main()
{
int n;
scanf("%d",&n);
static int A[1000000];
long long AA=0;
for(int i=0;i<n;i++){
scanf("%d",A+i);
AA+=A[i];
}
long long l=0,r=AA+1;
while(l+1<r){
long long m=(l+r)/2;
static long long S[1000000];
static int P[1000000];
for(int i=0;i<n;i++){
if(i>0){
P[i]=P[i-1]-1;
S[i]=S[i-1]-A[i-1];
}
else{
P[i]=0;
S[i]=0;
}
while(S[i]<m){
S[i]+=A[(i+P[i])%n];
P[i]++;
}
}
bool B=0;
for(int i=0;i<n;i++){
if(AA-S[i]-S[(i+P[i])%n]>=m){
B=1;
}
}
if(B){
l=m;
}
else{
r=m;
}
}
printf("%lld\n",l);
return 0;
}

/* Template the Final Chapter Light --- Fimbulvetr version 0.1 /
/ In this blizzard, I will find peace. */
# define LOCAL
# include <cstring>
# include <cstdio>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
using namespace std;
# define REP( i, n ) for ( int i = 1; i <= n; i ++ )
# define REP_0( i, n ) for ( int i = 0; i < n; i ++ )
# define REP_0N( i, n ) for ( int i = 0; i <= n; i ++ )
# define REP_S( i, ss ) for ( char *i = ss; *i; i ++ )
# define REP_G( i, u ) for ( int i = pos[ u ]; i; i = g[ i ].frt )
# define FOR( i, a, b ) for ( int i = a; i <= b; i ++ )
# define DWN( i, a, b ) for ( int i = b; i >= a; i -- )
# define RST( a ) memset ( a, 0, sizeof ( a ) )
# define CLR( a, x ) memset ( a, x, sizeof ( a ) )
# define CPY( a, b ) memcpy ( a, b, sizeof ( a ) )
typedef long long LL;
const int inf = 1 << 30;

# define NS 200100
int n;
LL a[ NS ], sum[ NS ];

bool Check ( LL len )
{
int mid = 0, nxt = 0;
REP_0 ( st, n )
{
while ( mid <= st + n && sum[ mid ] - sum[ st ] < len ) mid ++;
if ( mid <= st + n )
{
while ( nxt <= st + n && sum[ nxt ] - sum[ mid ] < len ) nxt ++;
if ( nxt <= st + n && sum[ st + n ] - sum[ nxt ] >= len ) return true;
}
}
return false;
}
int main ()
{
scanf ( "%d", &n );
REP ( i, n ) scanf ( "%lld", &a[ i ] ), sum[ i ] = sum[ i - 1 ] + a[ i ];
REP ( i, n ) sum[ i + n ] = sum[ i + n - 1 ] + a[ i ];
LL l = 0, r = 1LL << 60;
for ( ; l < r; )
{
LL mid = ( l + r + 1 ) / 2;
if ( Check ( mid ) ) l = mid;
else r = mid - 1;
}
printf ( "%lld\n", l );
return 0;
}

二分答案+前缀和+二分查找

二分查找呢