CF1380A.Three Indices

入门

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a permutation p1,p2,…,pnp_1, p_2, \dots, p_n. Recall that sequence of nn integers is called a permutation if it contains all integers from 11 to nn exactly once.

Find three indices ii, jj and kk such that:

  • 1≤i<j<k≤n1 \le i \lt j \lt k \le n;
  • pi<pjp_i \lt p_j and pj>pkp_j \gt p_k.

Or say that there are no such indices.

给你一个排列 p1,p2,…,pnp_1, p_2, \dots, p_n。回忆一下:若一个包含 nn 个整数的序列恰好包含从 11 到 nn 的所有整数各一次,则称其为一个排列。

请找出三个下标 ii、jj 和 kk,使得:

  • 1≤i<j<k≤n1 \le i \lt j \lt k \le n;
  • pi<pjp_i \lt p_j 且 pj>pkp_j \gt p_k。

若不存在满足条件的下标,则输出不存在。

输入格式

The first line contains a single integer TT (1≤T≤2001 \le T \le 200) — the number of test cases.

Next 2T2T lines contain test cases — two lines per test case. The first line of each test case contains the single integer nn (3≤n≤10003 \le n \le 1000) — the length of the permutation pp.

The second line contains nn integers p1,p2,…,pnp_1, p_2, \dots, p_n (1≤pi≤n1 \le p_i \le n; pi≠pjp_i \neq p_j if i≠ji \neq j) — the permutation pp.

第一行包含一个整数 TT(1≤T≤2001 \le T \le 200)——测试用例的数量。

接下来的 2T2T 行包含测试用例——每个测试用例占两行。每个测试用例的第一行包含一个整数 nn(3≤n≤10003 \le n \le 1000)——排列 pp 的长度。

每个测试用例的第二行包含 nn 个整数 p1,p2,…,pnp_1, p_2, \dots, p_n(1≤pi≤n1 \le p_i \le n;当 i≠ji \neq j 时,pi≠pjp_i \neq p_j)——排列 pp。

输出格式

For each test case:

  • if there are such indices ii, jj and kk, print YES (case insensitive) and the indices themselves;
  • if there are no such indices, print NO (case insensitive).

If there are multiple valid triples of indices, print any of them.

对于每个测试用例:

  • 如果存在满足条件的下标 ii、jj 和 kk,则输出 YES(不区分大小写)以及这些下标本身;
  • 如果不存在这样的下标,则输出 NO(不区分大小写)。

如果存在多个有效的下标三元组,输出其中任意一个即可。

输入输出样例

  • 输入#1

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

    输出#1

    YES
    2 3 4
    YES
    3 5 6
    NO

输入解题思路,AI测评打分。不知道怎么写?

首页