Submission #175234

---

Source Code Expand

//交換が一番文字の位置をずらさない方法である。
//あ、でも交換の後に並び替えないとWAするかも…
//最適な並べ替えをカウント前に行おう！！
#include<iostream>
#include<string.h>
#define rep(i,n) for(i = 0;i < n;i++)
#define repn(i,m,n) for(i = m;i < n;i++)
using namespace std;

int N,K;
char S[104],C[104];
char A[104];

void Memcpy( char *DIST,char *SRC,int N ){
	int i;
	rep(i,N){
		DIST[i] = SRC[i];
	}
}
int main(){
	int i,j,k,l;
	cin >> N >> K;
	cin >> S;
	rep( i,N ){
		A[i] = S[i];
	}
	rep( i,N )
	{
		char MIN = A[i];
		repn( j,i+1,N ){
			if( A[j] >= MIN )
				continue;
			//メモする
			Memcpy( C,A,N );
			//交換する
			//cout << A[pos] << " " << A[i] << endl;
			swap( A[j],A[i] );
			//i+1文字目から先をAとできるだけ一致するように貪欲に並び替え
			repn( k,i+1,N ){
				if( S[k] == A[k] )
					continue;
				repn(l,k+1,N ){
					if( A[l] == S[k] )
						swap( A[l],A[k] );
				}
			}
			//違う位置の文字を数えて、Kを超えたらもとに戻す
			int num = 0;
			rep(k,N){
				if( A[k] != S[k] )
					num++;
			}
			if( num > K ){
				Memcpy( A,C,N );
			}
			else{
				MIN = A[i];
			}
		}
	}
	cout << A << endl;
	return 0;
}

Submission Info

Judge Result