CF1270B.Interesting Subarray
普及-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
For an array a of integers let's denote its maximal element as max(a), and minimal as min(a). We will call an array a of k integers interesting if max(a)−min(a)≥k. For example, array [1,3,4,3] isn't interesting as max(a)−min(a)=4−1=3<4 while array [7,3,0,4,3] is as max(a)−min(a)=7−0=7≥5.
You are given an array a of n integers. Find some interesting nonempty subarray of a, or tell that it doesn't exist.
An array b is a subarray of an array a if b can be obtained from a by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.
对于一个整数数组 a,我们用 max(a) 表示其最大值,min(a) 表示其最小值。若一个包含 k 个整数的数组 a 满足 max(a)−min(a)≥k,则称该数组为有趣的。例如,数组 [1,3,4,3] 不是有趣的,因为 max(a)−min(a)=4−1=3<4;而数组 [7,3,0,4,3] 是有趣的,因为 max(a)−min(a)=7−0=7≥5。
给定一个长度为 n 的整数数组 a,请找出 a 的一个非空有趣子数组;若不存在,则说明不存在。
数组 b 是数组 a 的一个子数组,当且仅当 b 可通过从 a 的开头删除若干(可能为零或全部)元素、并从 a 的末尾删除若干(可能为零或全部)元素得到。特别地,一个数组是其自身的子数组。
输入格式
The first line contains integer number t (1≤t≤10000). Then t test cases follow.
The first line of each test case contains a single integer n (2≤n≤2⋅105) — the length of the array.
The second line of each test case contains n integers a1,a2,…,an (0≤ai≤109) — the elements of the array.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
第一行包含一个整数 t(1≤t≤10000)。随后是 t 组测试数据。
每组测试数据的第一行包含一个整数 n(2≤n≤2⋅105)—— 数组的长度。
每组测试数据的第二行包含 n 个整数 a1,a2,…,an(0≤ai≤109)—— 数组的元素。
保证所有测试数据的 n 之和不超过 2⋅105。
输出格式
For each test case, output "NO" in a separate line if there is no interesting nonempty subarray in a.
Otherwise, output "YES" in a separate line. In the next line, output two integers l and r (1≤l≤r≤n) — bounds of the chosen subarray. If there are multiple answers, print any.
You can print each letter in any case (upper or lower).
对于每个测试用例,如果数组 a 中不存在有趣的非空子数组,则在单独一行中输出 "NO"。
否则,在单独一行中输出 "YES";在下一行中输出两个整数 l 和 r(1≤l≤r≤n),表示所选子数组的边界。若存在多个答案,输出任意一个即可。
你可以以任意大小写(大写或小写)输出每个字母。
输入输出样例
输入#1
3 5 1 2 3 4 5 4 2 0 1 9 2 2019 2020
输出#1
NO YES 1 4 NO
说明/提示
In the second test case of the example, one of the interesting subarrays is a=[2,0,1,9]: max(a)−min(a)=9−0=9≥4.
在示例的第二个测试用例中,一个有趣的子数组是 a=[2,0,1,9]:max(a)−min(a)=9−0=9≥4。
输入解题思路,AI测评打分。不知道怎么写?