「Test」Sort

我太菜了。。 这都不会。。

首先可以直接知道他进行了几次完整的操作。

考虑剩下的位置

按权值从大到小考虑。

一个数只会被他前面的大的数交换

那么一个数要么在第一个空位上，要么在原来的位置上。

代码：

#include <bits/stdc++.h>

// Defination {{{
#define PI std::pair<int, int>
#define mk std::make_pair
#define reg register
#define ll long long
#define rep(i, a, b) for(reg int i = a; i <= b; ++i)
#define per(i, a, b) for(reg int i = a; i >= b; --i)
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
// }}}

template<typename T> T max(T a, T b) { return a > b ? a : b; }
template<typename T> T min(T a, T b) { return a < b ? a : b; }

template<typename T> void read(T &x) {
    x = 0; reg char ch = getchar(); reg int f = 1;
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    x *= f;
}

#define N 1000005

int n;
ll cnt;
int a[N], fa[N];
int b[N], Pos[N];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int main() {
    freopen ("sort.in", "r", stdin);
    freopen ("sort.out", "w", stdout);
    read(n), read(cnt);
    rep (i, 1, n) read(a[i]), Pos[a[i]] = i;
    int pos = n;
    rep (i, 1, n) {
        if (cnt < n - i) {
            pos = i - 1;
            break;
        }
        cnt -= n - i;
    }
    rep (i, 1, pos) {
        b[i] = i;
    }
    int tot = pos;
    per (i, n, pos + 1) {
        if (Pos[i] <= tot) {
            while (b[tot]) ++tot;
            b[tot] = i;
        } else {
            b[Pos[i]] = i;
        }
    }
    rep (i, pos + 1, n) {
        if (!cnt) break;
        rep (j, i + 1, n) {
            if (b[i] > b[j]) std::swap(b[i], b[j]);
            --cnt;
            if (!cnt) break;
        }
        if (!cnt) break;
    }
    rep (i, 1, n) printf("%d ", b[i]);
    puts("");
    return 0; 
}


/*
 _____  ____    _____
|__  / |  _ \  |__  /
  / /  | |_) |   / / 
 / /_  |  _ <   / /_ 
/____| |_| \_\ /____|
  

 ________________________________________ 
< sort.cpp is created by zrz who is weak >
 ---------------------------------------- 
        \   ^__^
         \  (^^)\_______
            (__)\       )\/\
             U ||----w |
                ||     ||

*/

赏

谢谢你请我吃薯片