codeforces 598 div3 Minimize the Permutation（贪心找规律）

题目大意：

有n个排列数。现在定义操作：

交换第i和i+1个元素。我们对每个i位置只能操作一次。问经过这种操作后，我们最少能够得到的字典序序列是多少。

解题思路：

我们贪心从小到大选择数往前挪，我们需要维护一个位置，这个位置是指我们从右到左最多只能移动到这个位置。有没有可能我们想把数字从左运动右呢？这里我们因为是字典序，每次只关心我们的目标数能不能放在前面，所以我们不关心能不能向右挪。另外我们挪动的时候假若中间遇到了比你小的数字，这时候就不要挪了。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int cas; cin >> cas;
  while (cas--) {
    int n; cin >> n;
    vector<int> arrmv(n);
    for (int i = 0; i<n; i++)cin >> arrmv[i];
    int swap_idx = 0;
    int pos, initpos;
    initpos = 0;
    int suc=0;
    for (int no = 1; no <= n; no++) {
      if (!suc)swap_idx = initpos;
      if (swap_idx == n - 1)break;
      suc = 0;
      for (int i = 0; i<n; i++) {
        if (arrmv[i] == no) {
          initpos = pos = i;
          break;
        }
      }
      if (pos <= swap_idx) { suc = 1; continue; }
      else {
        while (pos - 1 >= swap_idx && arrmv[pos - 1]>arrmv[pos]) {
          swap(arrmv[pos - 1], arrmv[pos]);
          pos--;
        }
      }   
    }
    for (auto it : arrmv) { cout << it << " "; }
    cout << endl;
  }
  return 0;
}