This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
与えられた数列を$nSwaps$回，隣り合う要素swap可能な時，辞書順最大になるようにする
最大値が一番左に来るのが一番良い．左から順番に要素を決めていく．新しく決める場所から，右にある要素を残りのswap回数で移動出来るかを大きい順に試す．移動可能であればswapしていき，そうでなければ次の要素を見る．これを繰り返して，試した前と変化が無ければそこで終了する．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
bool used [ 1000005 ];
class PartSorting {
public :
vector < int > process ( vector < int > data , int nSwaps ) {
int n = data . size ();
vector < int > v = data ;
sort ( v . begin (), v . end ());
memset ( used , 0 , sizeof ( used ));
int id = 0 ;
while ( nSwaps ) {
for ( int i = n - 1 ; i >= 0 ; i -- ) {
if ( used [ v [ i ]]) continue ;
int len = 0 ;
REP ( j , id , n ) {
if ( data [ j ] == v [ i ]) break ;
len ++ ;
}
if ( len <= nSwaps ) {
for ( int j = len - 1 ; j >= 0 ; j -- ) {
swap ( data [ id + j ], data [ id + j + 1 ]);
}
nSwaps -= len ;
used [ v [ i ]] = true ;
id ++ ;
break ;
} else continue ;
}
bool flag = true ;
rep ( i , n ) {
if ( used [ v [ i ]]) continue ;
flag = false ;
}
if ( flag ) break ;
}
return data ;
}
};