題目來源:
問題 - 2128B - Codeforces
這道題有些地方表達的并不是特別準確,首先就是從最左端與最右端移除一個元素,實際含義是從原數組的最左端或者最右段依次取出一個元素構成一個新的數組,使得這個新數組的數組符合題目的“好數組”要求。
既然如此,那么這道題就一目了然了,并且題目也說有多種答案輸出其中一種就可以,那我們就使用最粗暴的方法,利用雙指針依次對比左右兩端的數據,切換著輸出即可。
這里我們定義三個變量,r,l,k。r代表右端點的下標,l則是左端點的下標,k是計算有多少個元素被選中,方便結束循環與判斷什么時候輸出大的什么時候輸出小的。
當k為偶數時,判斷左端點右端點的大小,如果左端點更大就輸出L,否則輸出R,輸出哪個端點的大寫字母,那此時的小寫字母就要變化,左端點就+1,右端點就-1。
當k為奇數時,同樣判斷左右端點大小,這次不同的是如果左端點更小輸出L,這是為了保證不能連續增加或者連續減少,即使題目要求是連續5個遞增或遞減才是壞數組,比起計算有幾個連續遞增或者遞減,還是直接一大一小來的方便,最多只有2個是連續的。其余思路與k為偶數時相同。
#include<bits/stdc++.h>
using namespace std;
int main()
{int t;cin>>t;while(t--){int n;cin>>n;vector<int>arr(n);for(int i=0;i<n;i++){cin>>arr[i];}int k=0,l=0,r=n-1;while(1){if(k==n){break;}if(k%2==0){if(arr[l]>arr[r]){cout<<"L";//cout<<arr[l];l++;}else{cout<<"R";//cout<<arr[r];r--;}}else{if(arr[l]<arr[r]){cout<<"L";//cout<<arr[l];l++;}else{cout<<"R";//cout<<arr[r];r--;}}k++;}cout<<endl;}return 0;
}