CF1833D Flipper 题解

赛场上思路出来了但是代码没调出来。

首先考虑右端点，很明显，要让操作后的序列字典序尽量地大，那么就要使操作后的序列第一个数尽量地大，考虑 \(n\) 或 \(n-1\)，如果 \(n\) 在原序列的第一个位置，那么此时无论怎么调整都无法使得它在新序列的第一个位置，此时就要考虑让 \(n-1\) 在新序列的第一个位置，和 \(n\) 不在原序列的第一个位置类似，我们只要找到在原序列中的位置，然后 \(r\) 取这个位置的前一个即可。很明显，如果该数在原序列的末尾，那么 \(r\) 就应是 \(n\).

概述着说，就是右端点要找到 \([2,n]\) 中最大的数，若在末尾，则 \(r=n\)，反之 \(r\) 为最大数的前一个数。

接着考虑左端点，我们可以将新序列写成如下形式 \(r+1 \dots n \dots r \dots l \dots 1 \dots l-1\)，那么可以发现，当我们确定了右端点时，\(r+1\dots n\) 这一段就是确定了的，接下来就是要让 \(r \dots l \dots 1 \dots l-1\) 这一段尽量的大。因此我们首先要考虑让 \(l\) 尽量地大，那么很明显，若存在 \(a_i>a_{l-i}\)，那么此时 \(l\) 取 \(i\) 会是更优解。可以画图理解。

时间复杂度将近 \(O(n)\)，通过本题绰绰有余。

#include <cstdio>
#include <iostream>

using namespace std;

int t;
int n;
int a[2005];

int main() {
	scanf("%d",&t);
	while(t--) {
		scanf("%d",&n);
		int opt=0;
		for(int i=1;i<=n;i++) {
			scanf("%d",&a[i]);
			if(i>1&&a[i]>a[opt]) opt=i;//寻找[2,n]中最大数所在位置
		}
		if(n==1) {
			printf("%d\n",a[1]);
			continue;
		}
		int l=opt-1;
		int r=opt-1;//确定右端点
		if(opt==n) l=opt,r=opt;//同上
		for(int i=r-1;i>=1;i--) {//寻找最优左端点
			if(a[i]>=a[l-i]) l=i;
			else break;
		}
		for(int i=r+1;i<=n;i++) printf("%d ",a[i]);
		for(int i=r;i>=l;i--) printf("%d ",a[i]);
		for(int i=1;i<=l-1;i++) printf("%d ",a[i]);
		printf("\n");
	}
	return 0;
}