禅

全文第一行输入一个正整数 $T(1\le T\le10^5)$ ，表示数据组数。

对于每组数据，第一行输入一个正整数 $n(\color{red}1\le\color{black}n\le10^5,\sum n\le3\times10^6)$ 。

第二行输入 $n$ 个整数，第 $i$ 个表示 $a_i(\color{red}0\le \color{black}a_i\le10^9)$ 。

数据保证存在且仅存在一个 $i$ 满足 $a_i=0$ 。

pypy3 解法, 执行用时: 715ms, 内存消耗: 43996K, 提交时间: 2022-07-15 20:38:44

import sys
input=sys.stdin.readline  

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if n==1:
        print('No Solution')
        continue
    gz=a.index(0)
    ansr=ansl=max(a)+1
    right=0
    for i in range(gz)[::-1]:
        now=max(a[i]+1,right-a[i])
        right=now
        ansl=min(ansl,now)

    right=0
    for i in range(gz+1,n):
        now=max(a[i]+1,right-a[i])
        right=now
        ansl=min(ansl,now)
    print(ansl)

C++ 解法, 执行用时: 316ms, 内存消耗: 1428K, 提交时间: 2022-05-28 17:43:49

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N],g[N];
int t,n,k;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<n;i++)
		{
		scanf("%d",&g[i]);
		if(g[i]==0)
		k=i;
	}
	int ans=1e9;
	f[k]=0;
	for(int i=k-1;i>=0;i--)
    {f[i]=max(f[i+1]-g[i],g[i]+1);
	ans=min(ans,f[i]);}
	for(int i=k+1;i<n;i++)
    {f[i]=max(f[i-1]-g[i],g[i]+1);
	ans=min(ans,f[i]);}
	if(ans==1e9)
    cout<<"No Solution"<<endl;
    else
    cout<<ans<<endl;
}
return 0;
}

详情