Codeforces Round #656 (Div. 3) C. Make It Good
The array bb of length mm is called good, if you can obtain a non-decreasing array cc (c1≤c2≤⋯≤cmc1≤c2≤⋯≤cm ) from it, repeating the following operation mm times (initially, cc is empty):
For example, if we do 44 operations: take b1b1 , then bmbm , then bm−1bm−1 and at last b2b2 , then bb becomes [b3,b4,…,bm−3][b3,b4,…,bm−3] and c=[b1,bm,bm−1,b2]c=[b1,bm,bm−1,b2] .
Consider the following example: b=[1,2,3,4,4,2,1]b=[1,2,3,4,4,2,1] . This array is good because we can obtain non-decreasing array cc from it by the following sequence of operations:
1. take the first element of bb , so b=[2,3,4,4,2,1]b=[2,3,4,4,2,1] , c=[1]c=[1] ;
2. take the last element of bb , so b=[2,3,4,4,2]b=[2,3,4,4,2] , c=[1,1]c=[1,1] ;
3. take the last element of bb , so b=[2,3,4,4]b=[2,3,4,4] , c=[1,1,2]c=[1,1,2] ;
4. take the first element of bb , so b=[3,4,4]b=[3,4,4] , c=[1,1,2,2]c=[1,1,2,2] ;
5. take the first element of bb , so b=[4,4]b=[4,4] , c=[1,1,2,2,3]c=[1,1,2,2,3] ;
6. take the last element of bb , so b=[4]b=[4] , c=[1,1,2,2,3,4]c=[1,1,2,2,3,4] ;
7. take the only element of bb , so b=[]b=[] , c=[1,1,2,2,3,4,4]c=[1,1,2,2,3,4,4] — cc is non-decreasing.
Note that the array consisting of one element is good.
Print the length of the shortest prefix of aa to delete (erase), to make aa to be a good array. Note that the required length can be 00 .
You have to answer tt independent test cases.
Input
The first line of the input contains one integer tt (1≤t≤2⋅1041≤t≤2⋅104 ) — the number of test cases. Then tt test cases follow.
The first line of the test case contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105 ) — the length of aa . The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤2⋅1051≤ai≤2⋅105 ), where aiai is the ii -th element of aa .
It is guaranteed that the sum of nn does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105 ).
Output
For each test case, print the answer: the length of the shortest prefix of elements you need to erase from aa to make it a good array.
Example
Input
Copy
5
4
1 2 3 4
7
4 3 3 8 4 5 2
3
1 1 1
7
1 3 1 4 5 3 2
5
5 4 3 2 3
Output
Copy
0
4
0
2
3
수열 a를 정해서 좋은 수열로 만들려면 삭제해야 할 가장 짧은 접두사 길이를 구하는 것이다.그 중에서 좋은 수열의 정의는 매번 이 수열의 머리나 꼬리에서 하나의 수를 가져가서 c수열의 꼬리에 놓으면 최종적으로 c수열이 단조롭지 않게 된다는 것이다.
분명히 좋은 수열은 단조로워도 줄지 않는다/단조로워도 증가하지 않는다/먼저 단조로워도 줄지 않고 후에 단조로워도 증가하지 않는다. 예를 들어 1, 2, 3, 3, 2, 1.
또 삭제된 것은 접두사이며 단조로움이 증가하지 않고 단조로움이 줄지 않는 것은 마지막 상황에 포함되어 있기 때문에 수열의 끝부분에서 직접 앞으로 옮겨다니며 가장 긴 선단조로움이 줄지 않은 후 단조로움이 자열의 길이를 증가하지 않는 것을 찾아서 원래의 길이로 줄이면 된다.
#include
using namespace std;
int n, a[200005];
int main()
{
int t;
cin >> t;
while(t--)
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
int up = 1, hill = 1;
for(int i = n - 1; i >= 1; i--)
{
if(a[i] >= a[i + 1]) up++;
else break;
}
hill = up;
for(int i = n - up; i >= 1; i--)
{
if(a[i] <= a[i + 1]) hill++;
else break;
}
cout << n - hill << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.