题意

t

组数据，每组给定一个长度为

n

的数组

a_n

，要求通过移除最左段或最右段的元素进行重新排列，使得重新排列后的数组

q

满足任意

5

个元素不单调，输出一种方案。

思路

我们可以使用双指针

l

和

r

分别表示最左段和最右段的元素，并取

l

和

r

中的最值，然后更新端点，初始状态下我们可以先取最大值，用

flag

来表示上一次取的是最大值还是最小值，那么就有

2

种情况。

如果上次取的是最大值，即 $flag=1$ ，那么这一次我们就取最小值，并更新 $flag=0$ 。
如果上次取的是最小值，即 $flag=0$ ，那么这一次我们就取最大值，并更新 $flag=1$ 。

取完最值后，根据取的端点更新

l

和

r

直至

l>r

，最后输出

ans

即可。

证明

假设这一次我取的最大值是

a_l

，那么下一次我要取的最小值就是

a_{l+1}

和

a_r

两者中的一个，因为这一次我取的最大值是

a_l

，那么显然

a_l>a_r

，此时我们分为两种情况讨论。

$a_{l+1}<a_r$ ，那么我们就取 $a_{l+1}$ 为最小值，那么接下来就要在 $a_{l+2}$ 和 $a_r$ 之间取最大值。如果取 $a_{l+2}$ ，那么说明 $a_{l+2}>a_r>a_{l+1}$ ，显然满足不单调；如果取 $a_r$ ，同理也满足不单调。
$a_r<a_{l+1}$ ，显然同 $a_{l+1}<a_r$ 的情况。

综上，当我们不断取左右端点的最值时最后得到的排列肯定是不单调的，证毕。

Code

CPP

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
#define N 100086
using namespace std;
int t,n,a[N];
inline int read();
signed main(){
    t=read();
    while(t--){
        string ans;
        int f=0;
        n=read();
        for(int i=1;i<=n;i++) a[i]=read();
        int r=n;
        for(int i=1;i<=r;){
            if(!f){//初始状态或上一次取最小值时让f=0，以便这次取最大值
                if(a[r]>a[i]){
                    r--;
                    ans.push_back('R');
                }else ans.push_back('L'),i++;
                f=1;
            }else{//同上
                f=0;
                if(a[r]<a[i]){
                    r--;
                    ans.push_back('R');
                }else ans.push_back('L'),i++;//记得更新左右端点
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

题解：CF2128B Deque Process

文章操作

题意

思路

证明

Code

相关推荐

评论

题解：CF2128B Deque Process