1455 D. Sequence and Swaps(思维)

link

考虑枚举以 i i i位置作为开头而 j j j位置作为结尾位置,可以得到最后排序后的数组

那么扫描所有 a k ! = b k a_k!=b_k ak​!=bk​的索引 k k k

如果此时 a k < b k a_k

如果此时 a k = = b k a_k==b_k ak​==bk​,不需要管

如果此时 a k > b k a_k>b_k ak​>bk​,需要把 a k a_k ak​加入操作队列,且此时的操作前驱是数字 b i b_i bi​对应的索引位置

但是此时的复杂度比较劣,为 O ( n 3 l o g ( n ) ) O(n^3log(n)) O(n3log(n))

#include 
using namespace std;
const int maxn = 3e5+10;
int a[maxn],b[maxn],n,ans,x;
int main()
{
	ios::sync_with_stdio( false ); cin.tie( 0 ); cout.tie( 0 );
	int t; cin >> t;
	while( t-- )
	{
		cin >> n >> x;
		int ans = 1e9, flag = 1;
		for(int i=1;i<=n;i++)
		{
			cin >> a[i];
			if( a[i]v1,v2;
				for(int q=1;q<=n;q++)
				{
					if( a[q]==b[q] )	continue;
					res++;//为了把b[q]换过来 
					if( a[q]=1e9 )	break;
				sort( v1.begin(),v1.end() ); sort( v2.begin(),v2.end() );
				for(int i=0;in )	ans = -1;
		cout << ans << endl;
	}
}

正解就比较巧妙了emm

由于操作的实质,是选择一个递增的序列,整体往右移一个距离,且第一个位置变成 x x x

也就是 a x 1 , a x 2 . . . a x k = = > x , a x 1 . . . . a x k − 1 a_{x_1},a_{x_2}...a_{x_k} ==> x,a_{x_1}....a_{x_{k-1}} ax1​​,ax2​​...axk​​==>x,ax1​​....axk−1​​,整体减小

所以选定的索引满足 x < a x 1 < a x 2 . . . < a x k xx

x 1 < x 2 < x 3 . . . < x k x_1

所以操作一定是从前往后的(如果这都不能有序就无解)

注意到若存在 a i > x & & a j > x & & i < j a_i>x&&a_j>x&&ix&&aj​>x&&i

如果 a i a_i ai​不与 x x x交换,那么 a j a_j aj​也不会和 x x x交换

如果 a j a_j aj​坚持和 x x x交换,此时 a j = x < a i a_j=xaj​=x

所以只需要从前往后扫描,每次先检查数组是否已经有序,有的话就退出输出答案

否则检查当前 a i a_i ai​是否大于 x x x,如果大于就交换

#include 
using namespace std;
const int maxn = 3e5+10;
int a[maxn],b[maxn],n,ans,x;
int main()
{
	ios::sync_with_stdio( false ); cin.tie( 0 ); cout.tie( 0 );
	int t; cin >> t;
	while( t-- )
	{
		cin >> n >> x;
		for(int i=1;i<=n;i++)	cin >> a[i];
		int las = n;
		for(int i=n-1;i>=1;i--)
		{
			if( a[i]<=a[i+1] )	las = i;
			else	break;
		}
		int ans = 0;
		for(int i=1;i<=n;i++)
		{
			if( a[i]<=x )	continue;
			if( i>=las && a[i]>=a[i-1] )	break;
			swap( a[i],x ); ans++;
		}
		for(int i=2;i<=n;i++)
			if( a[i]