首页 > 其他分享 >Educational Codeforces Round 91 (Rated for Div. 2) A. Three Indices

Educational Codeforces Round 91 (Rated for Div. 2) A. Three Indices

时间:2023-10-15 22:44:50浏览次数:53  
标签:std Educational Rated int Codeforces 不妨

给一个 \(n\) 个整数的排列 \(p_1, p_2, \cdots, p_n\) ,需要找到三个数 \(i, j, k\) 满足:

  • \(1 \leq i < j < k \leq n\)
  • \(p_i < p_j\) , \(p_j < p_k\)

否则回答不可能。

\(key\) :若存在上述 \(i, j, k\) ,则存在 \(x\) 满足 \(p_{x - 1} < p_{x}, p_{x} > p_{x + 1}\) 。
证明:
已知任意 \(p_i\) 不同,假设 \(i, j, k\) 存在。

  • 若 \(p_{j + 1} > p_j\) 不妨让 \(j = j + 1\) ,若 \(p_{j + 1} < p_j\) 不妨让 \(k = j + 1\) 。
  • 若 \(p_{j - 1} > p_j\) 不妨让 \(j = j - 1\) ,若 \(p_{j - 1} < p_j\) 不妨让 \(i = j - 1\) 。

于是存在 \(x\) 满足 \(p_{x - 1} < p_{x}, p_{x} > p_{x + 1}\) 。

view
#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
	}
	for (int i = 2; i < n; i++) {
		if (a[i - 1] < a[i] && a[i + 1] < a[i]) {
			std::cout << "YES\n";
			std::cout << i - 1 << ' ' << i << ' ' << i + 1 << '\n';
			return;
		}
	}
	std::cout << "NO\n";
}

int main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
} 

标签:std,Educational,Rated,int,Codeforces,不妨
From: https://www.cnblogs.com/zsxuan/p/17766378.html

相关文章

  • * Codeforces Round 665 (Div. 2) A. Distance and Axis
    有一个点\(A\)在\(OX\)正坐标轴上的\(x\)坐标为\(n\)。需要找到一个点\(B\),使得\(||OB|-|AB||=k\)。现在给出非负整数\(n\)\(k\),你可以执行任意次以下操作:每步操作可以使\(A\)的坐标加一或减一。询问最少需要进过多少次操作使\(B\)可以存在。先假设出......
  • Landsat 8 Collection 2 Tier 1 calibrated top-of-atmosphere (TOA) reflectance
    Landsat8Collection2Tier1calibratedtop-of-atmosphere(TOA)reflectance.Calibrationcoefficientsareextractedfromtheimagemetadata.See Chanderetal.(2009) fordetailsontheTOAcomputation.Landsatsceneswiththehighestavailabledataqual......
  • Codeforces Round 903 (Div. 3)
    [比赛链接]A.Don'tTrytoCount直接用string的可加性,每次s+=s相当于翻倍了,因为\(nm<=25\)所以最多翻倍5次。判断什么的直接模拟就行。#include<iostream>#include<algorithm>#include<cmath>#include<cstdio>#include<cstring>#include<cstdlib>#inclu......
  • Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance(图论)
    CodeforcesRound903(Div.3)F.MinimumMaximumDistance思路对标记点更新fg,从0开始进行bfs,更新d1为所有点到0的距离获得到0最远的标记点L,从L开始bfs,更新d2为所有点到L的距离获得距离L最远的标记点R,从R开始bfs,更新d3为所有点到R的距离遍历所有点,这个点与标记点的最大距......
  • CodeForces 1886E I Wanna be the Team Leader
    洛谷传送门CF传送门把题意抽象成,给你长为\(n\)的序列\(a\)和长为\(m\)的序列\(b\),初始有\(m\)个空集合(可重集),\(a\)中的每个元素至多被分到\(m\)个集合中的一个。要求最后第\(i\)个集合\(T_i\)不为空,且\(\forallx\inT_i,x\ge\frac{b_i}{|T|}\)。要求构造......
  • Codeforces Round 671 (Div. 2) A. Digit Game
    \(R\)和\(B\)在玩一个数字游戏,给一个含有\(n\)位的正整数\(x\)。俩人轮流操作,\(R\)先行动。在每一步中,\(R\)可以选择\(x\)中一个未被标记的奇数位置并标记,\(B\)可以选择\(x\)中一个未被标记的偶数位置并标记。当最后只剩下一个未被标记的位置时,让这个数为\(m\)......
  • Codeforces Round 748 (Div. 3) B. Make it Divisible by 25
    给一个正整数\(n\),在一步操作中可以移除\(n\)中的一个。当\(n\)只剩下一位时将不能再操作,如果过程中产生了前导\(0\),则会被自动移除且不耗费操作次数。询问最少需要多少次操作可以使得\(n\)被\(25\)整除。显然一个正整数\(x\)若可以被\(25\)整除,只需要考虑最后......
  • Educational Codeforces Round 116 (Rated for Div. 2) A. AB Balance
    给一个长为\(n\)的字符串\(s\),只包含\(0\)\(1\)两种字符。定义\(AB(s)\)是\(s\)中出现的\(01\)子串个数,\(BA(s)\)是\(s\)中出现的\(10\)子串个数。在一步操作中,可以选择一个字符进行异或。询问最小的操作次数使得\(AB(s)=BA(s)\)。显然连续的\(11\)或连......
  • Codeforces Round 903 (Div. 3) E. Block Sequence(DP)
    CodeforcesRound903(Div.3)E.BlockSequence思路:设dp[i]为当i~n为完美的最少删除次数dp[n]=1,dp[n+1]=0;从后至前对于dp[i]更新若直接删除当前点,则为dp[i+1]+1若不删除则为min(dp[i+a[i]+1],dp[i]);i+a[i]+1为a[i]不能覆盖的位置#defineintlonglong#define......
  • Codeforces Round 903 (Div. 3)
    D题被hack了哭了第一题简单的只用把字符串重复的同时尝试匹配,然后判断就好了,只是需要一点代码能力第二题,也很简单最多剪断3次,就先从小到大排序,然后用最小的,看看大的是他的几倍,如果不是几倍的关系就不可能完成,如果是就算要几次就好了第三题,也很简单,很明显,对于一个格子,在它旋转9......