1300*B. Sort the Array(排序构造)

news/2024/7/20 13:59:39 标签: c语言, 算法, 开发语言, 深度优先, c++

题意:

        一个无重复数字的序列,能否反转一个区间使其成为单增序列。 

解析:

        记录每个点的值和初始下标,然后排序。

        对于排好序的序列进行遍历,找出第一段和原序列下标不同的区间并且标记(此区间即为翻转的区间),如果还出现其他的不同区间则不符题意。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int t,n,s;
struct node{
	int id,k;
	bool operator<(const node& t)const{
		return k<t.k;
	}
}a[N];
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i].k);
		a[i].id=i;
	}
	sort(a+1,a+n+1);
	int l=-1,r,f=1;
	for(int i=1;i<n;i++){
		if(a[i].id!=i){
			s=1;
			if(l==-1){
				l=i,r=i;
				int p=a[i].id;
				for(int j=i+1;j<=n;j++){
					if(a[j].id==p-1) r++,p--;
					else break;
				}
				i=r;
			}
			else{
				f=0;
				break;
			}
		}
	}
	if(!s) l=r=1;
	if(f) cout<<"yes"<<endl<<l<<" "<<r;
	else cout<<"no";
	return 0;
}

http://www.niftyadmin.cn/n/5067530.html

相关文章

云原生Kubernetes:K8S集群kubectl命令汇总

目录 一、理论 1.概念 2. kubectl 帮助方法 3.kubectl 子命令使用分类 4.使用kubectl 命令的必要环境 5.kubectl 详细命令 一、理论 1.概念 kubectl是一个命令行工具&#xff0c;通过跟 K8S 集群的 API Server 通信&#xff0c;来执行集群的管理工作。 kubectl命令是操…

基于SpringBoot的高考志愿填报系统

功能需求&#xff1a; 1.用户可以根据自己的院校类型、办学类型、层次类型、地域等因素筛选高校。 2.用户可以查询到所选高校的基本信息&#xff0c;包括学校的概况、历史沿革、办学特色、学院设置、师资力量、科研实力等。 3.用户可以查询到所选高校的高校开设专业&#xff0c…

Redis-双写一致性

双写一致性 双写一致性解决方案延迟双删&#xff08;有脏数据的风险&#xff09;分布式锁&#xff08;强一致性&#xff0c;性能比较低&#xff09;异步通知&#xff08;保证数据的最终一致性&#xff0c;高并发情况下会出现短暂的不一致情况&#xff09; 双写一致性 当修改了数…

CYEZ 模拟赛 8

A 求出第 i i i 个点在矩形中的最早时间 l i l_i li​ 和最晚时间 r i r_i ri​。 对坐标离散化&#xff0c;在时间轴上做差分。由于答案相等时要求时间最小&#xff0c;故答案一定会在 l l l 处取到。 B C 两张 n n n 个点的二分图 A B&#xff0c; ( x , y ) 1 (x…

评分和排名算法

排名是非常高频的需求&#xff0c;通常伴随着某种决策行为&#xff0c;比如投资行为&#xff0c;比赛投注行为&#xff0c;商品选购&#xff0c;等等。排名的对象五花八门&#xff0c;理财产品&#xff0c;参赛队伍&#xff0c;商品&#xff0c;网页&#xff0c;视频&#xff0…

【每日一题】买卖股票的最佳时机含冷冻期

文章目录 Tag题目来源题目解读解题思路方法一&#xff1a;动态规划空间优化 写在最后 Tag 【动态规划】【数组】【2023-10-05】 题目来源 309. 买卖股票的最佳时机含冷冻期 题目解读 这是股票系列问题的第五篇了&#xff0c;要求求出买卖股票的最佳时期以获得最大的利润&…

k8s集群-7 service

工作负载的应用是如何暴露出去的 解决访问问题 Service可以看作是一组提供相同服务的Pod对外的访问接口。借助Service&#xff0c;应用可以方便地实现服务发现和负载均衡。 service默认只支持4层负载均衡能力&#xff0c;没有7层功能。(可以通过Ingress实现) service的类型: C…

2.证明 非单一点 Oct.2023

目录 原题解引申出的编程问题非单一点题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 题解题目正解 原题 已知等边 Δ P 0 P 1 P 2 \Delta P_0P_1P_2 ΔP0​P1​P2​&#xff0c;它的外接圆是 O O O&#xff0c;设 O O O的半径是 R R R。同时&#xff0c;设 Δ …