题解：CF2156F1 Strange Operation (Easy Version)

答案中的

1

在哪？

在最靠前的同时作为前缀最小值的奇数处。我们把它先操作成

1

，剩下的所有数相对大小全部不变。因此我们可以把这个元素扔掉，就贪心地变成

n-1

的子问题了。

复杂度

O(n^2)

。

Code

CPP

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

题解：CF2156F1 Strange Operation (Easy Version)

文章操作

相关推荐

评论

题解：CF2156F1 Strange Operation (Easy Version)