Codeforces Round #656 (Div. 3) C. Make It Good

5672 단어
You are given an array aa consisting of nn integers. You have to find the length of the smallest (shortest) prefix of elements you need to erase from aa to make it a good array. Recall that the prefix of the array a=[a1,a2,…,an]a=[a1,a2,…,an] is a subarray consisting several first elements: the prefix of the array aa of length kk is the array [a1,a2,…,ak][a1,a2,…,ak] (0≤k≤n0≤k≤n ).
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):
  • select either the first or the last element of bb , remove it from bb , and append it to the end of the array cc .

  • 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;
    }

    좋은 웹페이지 즐겨찾기