列表

详情


NC23975. 区间

描述

小猫在研究序列。
小猫在研究单调性。
给定一个长度为 N 的序列 a_1,a_2,…,a_N ,请你选出一个最长的区间 [l,r](1≤l≤r≤N),满足a+l≤a_{l+1}≤…≤a_r
如果有多个,请输出l最小的。

输入描述

第一行一个正整数 T,表示数据组数。
每组数据的第一行一个正整数 N
接下来一行 N 个正整数 a_1,a_2,…,a_N

输出描述

T 行,每行两个正整数 l,r,表示选出的区间。

示例1

输入:

4
5
1 2 3 4 5
5
5 4 3 2 1
5
5 3 4 1 2
5
3 4 5 1 2

输出:

1 5
1 1
2 3
1 3

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C(clang 3.9) 解法, 执行用时: 125ms, 内存消耗: 4088K, 提交时间: 2019-05-04 14:08:01

#include<stdio.h>
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,a[1000],i;
		scanf("%d",&n);
		int l,t,max=0,m;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			if(i==0||a[i-1]>a[i])
			m=1,t=i;
			else m++;
			if(m>max)
			{
				l=t;
				max=m;
			}
		}
		printf("%d %d\n",l+1,l+max);
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 166ms, 内存消耗: 680K, 提交时间: 2022-12-02 20:23:02

#include"iostream"
using namespace std;
int main()
{
int t,n;
cin>>t;
while(t-->0)
{
cin>>n;
int i,a[n],l,r,h,d;
d=l=0;h=r=0;
for( i=0;i<n;i++)
cin>>a[i];
for(i=1;i<n;i++)
{if(a[i-1]<=a[i])   h++;
  else h=0;  
 if(h>(r-l))  {l=i-h;r=i;}
}   
cout<<l+1<<' '<<r+1<<endl;
}
}

C++(g++ 7.5.0) 解法, 执行用时: 165ms, 内存消耗: 412K, 提交时间: 2022-12-03 17:28:23

#include<iostream>
using namespace std;
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
int i,a[n],l,r,h,d;
d=l=0;h=r=0;
for( i=0;i<n;i++)
cin>>a[i];
for(i=1;i<n;i++)
{if(a[i-1]<=a[i])   h++;
  else h=0;  
 if(h>(r-l))  {l=i-h;r=i;}
}   
cout<<l+1<<' '<<r+1<<endl;
}
}

C++14(g++5.4) 解法, 执行用时: 262ms, 内存消耗: 348K, 提交时间: 2019-04-14 22:55:26

#include<iostream>
using namespace std;
int main()
{
	int n,i,t,tt,m,a,l,r;
	cin>>n;
	while(cin>>n)
	{
		for(i=a=m=l=r=1;i<=n;i++)
			cin>>t,i>1&&(t<tt?m=1:m++,m>a&&(r=i,l=i-m+1,a=m)),tt=t;
		cout<<l<<" "<<r<<endl;
	}
	return 0;
}

上一题