首页 > 其他分享 >【CF1833D】题解

【CF1833D】题解

时间:2023-05-20 22:33:56浏览次数:55  
标签:CF1833D 最大 int 题解 -- 区间 翻转

本文章同步发表于洛谷

思路

这是一道水题,但细节很多......

首先,要求字典序最大,显然就想到了让最大的数字在第一位。

于是就进一步得出了应该让最大数字在翻转区间的后一位,初步得出了以下思路:

  • 找到最大的数(\(n\))所在位置 \(r\),将 \(r-1\);
  • 贪心的寻找 \(r-1\) 以前第一个比 \(p_1\) 小的位置 \(l\);
  • 将 \(l+1\);
  • 输出区间。

第一个细节

当然,这是有问题的,因为如果 \(r=n\),则也有翻转区间 \([n,n]\) 的可能(参考第 \(2\) 个样例)。

所以,当 \(r=n\) 时,我们不进行 \(r-1\) 这个操作。

第二个细节

但这仍然有问题,如果 \(r=1\) 时,翻转区间将是 \([l,0]\),这个操作是无效的,于是可以想一下,哪个排列开头在不是最大的数时字典序最大呢?

那只能以 \(n-1\)(次大的数)作为开头了。

我们就要寻找 \(n-1\) 所在位置,再重复以上操作。

参考代码

#include<bits/stdc++.h>
using namespace std;
int t,n,p[2010];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		int l,r;
		for(int i=1;i<=n;i++){
			scanf("%d",&p[i]);
			if(p[i]==n) r=i;
		}
		if(r==1){
			for(int i=1;i<=n;i++){
				if(p[i]==n-1) r=i;
			}
		}
		if(r!=n) r--;
		l=r;
		for(int i=r-1;i>=1;i--){
			if(p[i]>p[1]) l--;
			else break;
		}
		for(int i=r+1;i<=n;i++) printf("%d ",p[i]);
		for(int i=r;i>=l;i--) printf("%d ",p[i]);
		for(int i=1;i<l;i++) printf("%d ",p[i]);
		putchar('\n');
	}
	return 0;
}

点赞关注一下再走呗qwq

标签:CF1833D,最大,int,题解,--,区间,翻转
From: https://www.cnblogs.com/fengxiaoyi/p/17417930.html

相关文章

  • 【题解】CF193D Two Segments
    题意给定一个\(1\simN\)的排列,在这个排列中选出两段互不重叠的区间,求使选出的元素排序后构成公差为1的等差数列的方案数。选出的两段区间中元素构成的集合相同时视为同一种方案。\(1\leN\le3\times10^5\)。传送门分析如果考虑怎么优化枚举的两个区间的话,发现不太好搞(反正......
  • jre jdk更改目录后Java无法运行问题解决方案
    问题:在将Java文件(包含jdkjre)由C盘直接剪贴到D盘后,所有Java程序无法运行,且其Java图标不再显示。解决方案:首先更改环境变量。当我们单纯地将Java文件更改位置后,我们计算机的环境变量仍未改变,依旧是当时安装Java时的配置。步骤:控制面板—>系统和安全—>系统—>高级系统设置—>环境......
  • P5179 Fraction 题解
    题目描述给你四个正整数\(a,\,b,\,c,\,d\),求一个最简分数\(\frac{p}{q}\)满足\(\frac{a}{b}<\frac{p}{q}<\frac{c}{d}\)。若有多组解,输出\(q\)最小的一组,若仍有多组解,输出\(p\)最小的一组。前置知识:Stern-Brocot树首先引入分数逼近。这里的分数逼近是指用用一个......
  • CF1781F题解
    \(\text{link}\)。也是一道非常巧妙的\(\texttt{dp}\)。容易想到把括号变成\(\pm1\)。考虑括号序列合法等价于前缀和\(\ge0\),我们可以想加入\(()\)或\()(\)对前缀的影响。设加入的位置的前一位前缀和为\(x\),则加入\(()\)相当于把\(x\)替换为\([x,x+1,x]\),加入......
  • CSP-J2021试题题解
    1.分糖果原题:https://www.luogu.com.cn/problem/P7909原代码:#include<bits/stdc++.h>#definelllonglongusingnamespacestd;lln,l,r;intmain(){ cin>>n>>l>>r; if(r%n==n-1)cout<<n-1; elseif(l%n==n-1)cout<<n-1; elseif(......
  • 问题解一
    (1)用pycharm连接mysql时,需要安装一个驱动,点击连接界面,如果TestConnection不可用,点击右边的按钮即可(2)如果要将同一网站不同链接的数据存入数据库,可考虑重写start_requestseg:forindex,hrefinenumerate(self.start_urls):ifindex==0:yieldscrapy.Request(......
  • 僵尸进程问题解决
    1何为僵尸进程僵尸进程是当子进程比父进程先结束,而父进程又没有回收子进程,释放子进程占用的资源,此时子进程将成为一个僵尸进程。如果父进程先退出,子进程被init接管,子进程退出后init会回收其占用的相关资源。在UNIX系统中,一个进程结束了,但是它的父进程没有等待(调用wait/wai......
  • 【P4331 [BalticOI 2004]】Sequence 数字序列 题解(左偏树维护动态区间中位数)
    左偏树维护动态区间中位数。传送门P4331BalticOI2004Sequence数字序列。Solution1我的思路和题解前半部分完全重合了((如果按照单调不增去分割\(a\)序列的话,对于每一段我们能很简单地得出它的最佳答案:中位数。发现严格单调很难做,很难拿捏,考虑对\(a\)序列的每一项都进......
  • CSP-J2022山东补赛题解
    1.植树节原题:https://www.luogu.com.cn/problem/U285015代码:#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=1e6+255;inta[N],n,x,y,maxb=-1e9,ans=-1e9;intmain(){ cin>>n; for(inti=1;i<=n;i++){ cin>>x&g......
  • CSP-J2019试题题解
    1.数字游戏原题:https://www.luogu.com.cn/problem/P5660代码:#include<bits/stdc++.h>#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;strings;intmain(){ cin>>s;intnum=0; fo......