丢手绢

第一行一个整数N，表示有N个小朋友玩丢手绢的游戏。
接下来的第2到第n行，第i行有一个整数，表示第i-1个小朋友顺时针到第i个小朋友的距离。
最后一行是第N个小朋友顺时针到第一个小朋友的距离。

C++(clang++ 11.0.1) 解法, 执行用时: 32ms, 内存消耗: 700K, 提交时间: 2022-10-18 16:08:06

#include<iostream>
using namespace std;
int a[200000];
int main(){
	int sum=0,n,i,j,res=0,cnt;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
	}j=0;cnt=0;
	for(i=0;i<n;i++){
		while(cnt<sum/2){
			cnt+=a[j++%n];
		}
		res=max(res,min(sum-cnt,cnt));
		cnt-=a[i];
	}cout<<res;
}

Python3 解法, 执行用时: 450ms, 内存消耗: 9052K, 提交时间: 2023-07-26 12:27:00

n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
s=sum(a)
j=0;ans=0;cnt=0
for i in range(n):
    cnt+=a[i]
    while j<=i and s-cnt<cnt:
        ans=max(ans,s-cnt)
        cnt-=a[j]
        j+=1
    ans=max(ans,cnt)
print(ans)

详情