题目来源:
问题 - 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;
}