题解：CF2156F1 Strange Operation (Easy Version)

· · 题解

答案中的 1 在哪？

在最靠前的同时作为前缀最小值的奇数处。我们把它先操作成 1，剩下的所有数相对大小全部不变。因此我们可以把这个元素扔掉，就贪心地变成 n-1 的子问题了。

复杂度 O(n^2)。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 1000005

int n,k,a[MAXN],r[MAXN],ans[MAXN];

inline void solve(){
    scanf("%lld",&n);
    for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&r[i]);
    for( int t = 1 ; t <= n ; t ++ ){
        int minn = n + 1;
        for( int i = 1 ; i <= n ; i ++ ){
            if( r[i] % 2 && r[i] < minn ){
                for( int j = 1 ; j <= n ; j ++ ) if( r[j] > r[i] ) r[j] --;
                ans[i] = t,r[i] = (int)1e9;
                break;
            }
            minn = min( minn , r[i] );
        }
    }
    for( int i = 1 ; i <= n ; i ++ ) printf("%lld ",ans[i]); puts("");
}

signed main(){
    int testcase; scanf("%lld",&testcase);
    while( testcase -- ) solve();
    return 0;
}

::::