$$sort$$

$正解部分$

第一个 $for$ 循环完成第 $i$ 次循环之后 $i$ 会到位置 $i$,
所以可以考虑先处理出完成尽可能多的第一个 $for$ 循环后的 { a i } {a_i} {ai​}, 剩下的操作暴力处理,
现在的问题就是 $(k,N]$ 的数字形式是什么,
设完成了 $k$ 次, 然后考虑 $(k,N]$ 的数字怎么填,
首先设 $a_i$ 的位置为 $p_i$, 现在处理 $a_i\in (k,N]$ 放哪些位置, 从大到小 处理,

• 当 $p_i>k$ 时, 位置只可能往后移 .
• 当 $p_i\le k$ 时, 其会被交换到 $(k,N]$ 中第一个空位 .

由于是 从大到小 枚举, 所以 较大的数字 放置了之后, 不会被 较小的数字 交换到其它位置了, 相当于位置固定了 .

$实现部分$

#include<bits/stdc++.h>
#define reg register

const int maxn = 1e6 + 5;

int N;
int A[maxn];
int p[maxn];
int vis[maxn];

long long cnt;

int main(){
        scanf("%d%lld", &N, &cnt);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &A[i]), p[A[i]] = i;
        for(reg int i = 1; i <= N; i ++)
                if(cnt >= N-i) cnt -= N-i;
                else{
                        for(reg int j = 1; j < i; j ++) A[j] = j;
                        int t = i;
                        for(reg int j = N; j >= i; j --){
                                if(p[j] >= i && !vis[p[j]]) vis[p[j]] = 1;
                                else{ 
                                        while(vis[t] && t <= N) t ++;
                                        vis[t] = 1; A[t] = j;
                                }
                        }
                        t = 0;
                        for(reg int j = i+1; j <= N; j ++){
                                if(A[j] < A[i]) std::swap(A[i], A[j]);
                                if(++ t >= cnt) break ;
                        }
                        break ;
                }
        for(reg int i = 1; i <= N; i ++) printf("%d ", A[i]);
        return 0;
}

最后

以上就是幸福香水为你收集整理的zzq's sort [思维题] s o r t sort sort的全部内容，希望文章能够帮你解决zzq's sort [思维题] s o r t sort sort所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。