深渊水妖

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

每组数据第一行输入一个正整数 $n(2\le n\le10^5)$ 。

第二行输入 $n$ 个正整数，第 $i$ 个正整数是 $a_i(1\le a_i\le n)$ 。

数据保证 $\sum n\le3\times10^6$ ，保证至少存在一个 $i\in[2,n]$ 满足 $a_i\ge a_{i-1}$ 。

pypy3 解法, 执行用时: 1186ms, 内存消耗: 44088K, 提交时间: 2022-01-26 22:23:26

for _ in range(int(input())):
    d=int(input())
    a=list(map(int,input().split()))+[-1]
    lst=0
    cur=0
    ans={}

    for i in range(1,d+1):
        if a[i]>=a[i-1]:
            cur=i
        else:
            c=a[i-1]-a[lst]
            if c not in ans:
                ans[c]=[]
            ans[c].append([lst+1,i])
            lst=i
            cur=i
    ANS=[]
    for x,y in sorted(ans[max(ans)]):
        ANS.append(x)
        ANS.append(y)
    print(*ANS)

C++ 解法, 执行用时: 560ms, 内存消耗: 1836K, 提交时间: 2022-02-20 11:13:00

#include<iostream>
using namespace std;
void solve()
{
	int n,a[100005],l[100005];
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i],l[i]=0;
	int maxvalue=0,t=1;
	for(int i=1;i<=n;i++)
	{
		if(a[i+1]<a[i]||i==n)
		{
			l[i]=t;
			t=i+1;
			if(a[i]-a[l[i]]>maxvalue)
			maxvalue=a[i]-a[l[i]];
		}
	}
	for(int i=1;i<=n;i++)
	if(l[i]>0&&a[i]-a[l[i]]==maxvalue)
	cout<<l[i]<<" "<<i<<" ";
	cout<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	solve();
	return 0;
}

详情