贴一段ppt
考虑模拟出这个算法进行k轮（即外层的i循环到k）时的序列，之后再暴力模拟零散的步。
考虑这个算法在01序列上的表现，k轮后实际上就是将最开始的不超过k个0放到序列开头。
考虑把序列转化成01序列，我们只要从1~n枚举x，然后把<=x的记为0，>x的记为1就行了，新增的那个0就是x的位置。
我们用priority_queue维护序列中当前前k个0的位置，每次考虑新的那个0的位置。
如果它为前k个，那么被弹出去的那个元素就是现在x的位置。如果它不为前k个，那么x的位置保持不变。
因为这题太过神仙我不知道咋讲了，感性理解吧（逃
#include<iostream> #include<cstdio> #include<queue> #include<cstring> namespace io { const int SIZE = (1 << 21) + 1; char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr; // getchar #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++) // print the remaining part inline void flush () { fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; } // putchar inline void putc (char x) { *oS ++ = x; if (oS == oT) flush (); } // input a signed integer template <class I> inline void gi (I &x) { for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1; for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f; } // print a signed integer template <class I> inline void print (I &x) { if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x; while (x) qu[++ qr] = x % 10 + '0', x /= 10; while (qr) putc (qu[qr --]); } //no need to call flush at the end manually! struct Flusher_ {~Flusher_(){flush();}}io_flusher_; } using io :: gi; using io :: putc; using io :: print;//题目附送的快读 using namespace std; #define N 1000005 priority_queue <int> h; int n,x,p[N],a[N]; long long k; void work(int x){ for(int i=1;i<=n;++i) p[a[i]]=i; for(int i=1;i<x;++i) a[i]=i,h.push(p[i]); for(int i=x;i<=n;++i){ if(h.top()<p[i]) a[p[i]]=i;//后面的一段不受影响 else{ a[h.top()]=i; h.pop(); h.push(p[i]); }//把i放到最右边的位置上 } } int main(){ freopen("sort.in","r",stdin); freopen("sort.out","w",stdout); gi(n);gi(k); for(int i=1;i<=n;++i) gi(a[i]); for(int i=1;i<=n;++i){ if(k>n-i) k-=n-i; else{ if(i>1) work(i); for(int j=i+1;j<=i+k;++j)//模拟零散步 if(a[j]<a[i]) swap(a[i],a[j]); for(int j=1;j<=n;++j) print(a[j]),putc(' '); return 0; } } }