别让猴子发烧了，它需要退烧（大雾
先假设我们不会
（侵权请联系删除。）
我们可以看到上面视频中最后一个排序并没有排完。
那就是大名鼎鼎的猴子排序（都听过吧）。
猴子排序是这样的：
- 给序列 random_shuffle；
- 判断序列是否有序；
- 重复执行直到直到有序。
这真是一个聪明的办法！
其时间复杂度期望是
所以这个猴子发烧了开始瞎随机。
我们需要给它退烧。
怎么退烧呢？
用退火就好啦！
具体的，每次随机交换两个元素，然后判断是不是更好，更好就直接换，否则有一定概率换。
诶，我们怎么判断是不是更好呢？诶对了，聪明的猴子们肯定想到了逆序对。
我们只需要让逆序对更少，就代表更好，是吧。
所以我们得到的以下代码（再说一遍，离散化不算！！！）：
// 模拟退火+逆序对优化猴子排序，仅供娱乐
#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
int in()
{
int k=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
return k*f;
}
void out(int x)
{
if(x<0)putchar('-'),x=-x;
if(x<10)putchar(x+'0');
else out(x/10),putchar(x%10+'0');
}
const int N=1e5+10;
struct bit
{
int c[N],n;
void init(int _n){n=_n;for(int i=0;i<=n+1;i++)c[i]=0;}
void add(int i,int v){for(;i<=n;i+=(i&-i))c[i]+=v;}
int ask(int i){int s=0;for(;i;i-=(i&-i))s+=c[i];return s;}
}T;
int a[N],n,m;
vector<int>A;
void input()
{
n=in();
for(int i=1;i<=n;i++)a[i]=in(),A.push_back(a[i]);
sort(A.begin(),A.end()),A.erase(unique(A.begin(),A.end()),A.end());
m=A.size();
for(int i=1;i<=n;i++)a[i]=lower_bound(A.begin(),A.end(),a[i])-A.begin()+1;
}
int calc()
{
T.init(m),T.add(a[n],1);
int ans=0;
for(int i=n-1;i>=1;i--)
{
ans+=T.ask(a[i]-1);
T.add(a[i],1);
}
return ans;
}
typedef long double ld;
const ld maxT=60000,eps=1e-10,D=0.95;
int ans=0;
void solve()
{
if(ans==0)return;
for(ld T=maxT;T>eps;T*=D)
{
if(clock()>=0.9*CLOCKS_PER_SEC)break;
int l=rand()%n+1,r=rand()%n+1;
while(l==r)l=rand()%n+1,r=rand()%n+1;
swap(a[l],a[r]);
int k=calc();
if(k<ans)ans=k;
else if(exp((ans-k)/T)*RAND_MAX<=(ld)rand())swap(a[l],a[r]);
if(ans==0)break;
}
}
int main()
{
srand(114514),input(),ans=calc();
while(clock()<0.9*CLOCKS_PER_SEC&&ans)solve();
for(int i=1;i<=n;i++)out(A[a[i]-1]),putchar(' ');
return 0;
}诶这个代码已经很优秀了，在
但是。
但是但是。
但是但是但是。
但是这个代码在
我们需要优化。
诶，通过观察可知，我们求逆序对太慢了，求一次要
这也就意味着退火退不了几次就要退出了。
考虑加速求逆序对。
诶呀然后猴子们找到了这个题。
就把一次求逆序对的时间降为了
我们就有以下代码（再再再说一遍，离散化不算！！！）：
// 模拟退火+动态逆序对优化猴子排序，仅供娱乐
#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
int in()
{
int k=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
return k*f;
}
void out(int x)
{
if(x<0)putchar('-'),x=-x;
if(x<10)putchar(x+'0');
else out(x/10),putchar(x%10+'0');
}
const int N=1e5+10;
int root[N],tot=0;
int n,m;
namespace qwq
{
struct Segtree{int lc,rc,v;}tree[N<<8];
int newnode()
{
tot++,tree[tot].lc=tree[tot].rc=tree[tot].v=0;
return tot;
}
void modify(int &k,int l,int r,int x,int z)
{
if(!k)k=newnode();
if(l==r)return tree[k].v+=z,void();
int mid=(l+r)>>1;
if(x<=mid)modify(tree[k].lc,l,mid,x,z);
else modify(tree[k].rc,mid+1,r,x,z);
tree[k].v=tree[tree[k].lc].v+tree[tree[k].rc].v;
}
int query(int k,int l,int r,int x,int y)
{
if(!k)return 0;
if(l>y||r<x)return 0;
if(l>=x&&r<=y)return tree[k].v;
int mid=(l+r)>>1;
return query(tree[k].lc,l,mid,x,y)+query(tree[k].rc,mid+1,r,x,y);
}
void insert(int x,int y,int z){for(;x<=n;x+=x&-x)modify(root[x],1,n,y,z);}
int sum(int x,int y,int l,int r)
{
int res=0;
for(;y;y-=y&-y)res+=query(root[y],1,n,l,r);
for(x--;x;x-=x&-x)res-=query(root[x],1,n,l,r);
return res;
}
}
int a[N],now=0;
vector<int>A;
void input()
{
n=in();
for(int i=1;i<=n;i++)a[i]=in(),A.push_back(a[i]);
sort(A.begin(),A.end()),A.erase(unique(A.begin(),A.end()),A.end());
m=A.size();
for(int i=1;i<=n;i++)a[i]=lower_bound(A.begin(),A.end(),a[i])-A.begin()+1;
for(int i=1;i<=n;i++)qwq::insert(i,a[i],1);
for(int i=2;i<=n;i++)now+=qwq::sum(1,i-1,a[i]+1,m);
}
int calc(int l,int r)
{
if(l>r)swap(l,r);
now-=qwq::sum(l+1,r-1,1,a[l]-1);
now+=qwq::sum(l+1,r-1,a[l]+1,m);
now-=qwq::sum(l+1,r-1,a[r]+1,m);
now+=qwq::sum(l+1,r-1,1,a[r]-1);
if(a[l]<a[r])now++;
if(a[l]>a[r])now--;
qwq::insert(l,a[l],-1);
qwq::insert(l,a[r],1);
qwq::insert(r,a[l],1);
qwq::insert(r,a[r],-1);
swap(a[l],a[r]);
return now;
}
typedef long double ld;
const ld maxT=60000,eps=1e-10,D=0.95;
int ans=0;
void solve()
{
if(ans==0)return;
for(ld T=maxT;T>eps;T*=D)
{
if(clock()>=0.9*CLOCKS_PER_SEC)break;
int l=rand()%n+1,r=rand()%n+1;
while(l==r)l=rand()%n+1,r=rand()%n+1;
int k=calc(l,r);
if(k<ans)ans=k;
else if(exp((ans-k)/T)*RAND_MAX<=(ld)rand())calc(l,r);
if(ans==0)break;
}
}
int main()
{
srand(114514),input(),ans=now*3;
while(clock()<0.9*CLOCKS_PER_SEC&&ans)solve();
for(int i=1;i<=n;i++)out(A[a[i]-1]),putchar(' ');
return 0;
}原谅我抄了这篇题解的代码。（侵权请联系删除）
这样在 （好像没高多少）。
诶但是在
它在我们的模板题中能拿到
这些猴子现在已经是低烧状态了！
难道我们猴子退不了烧了吗？难道随机化真的止步于此了吗？
是的。
update on 2025-03-31：
感谢 @x383494 提供的进一步优化：
复杂度瓶颈在于求逆序对。
我们考虑模拟退火的时候交换
这样我们可以不用求逆序对个数，而是直接在
这是其本人的代码：
// 看到 https://www.luogu.com.cn/article/4m9484d8 后有感而作
// 模拟退火优化猴排
// 可以通过 n<1e3 的数据
#include <iostream>
#include <cmath>
#include <random>
#define UP(i,s,e) for(auto i=s; i<e; i++)
#define DOWN(i,e,s) for(auto i=e; i-->s;)
using std::cin; using std::cout;
std::mt19937 rng(std::random_device{}());
std::uniform_real_distribution<> unif(0., 1.);
namespace m{ // }{{{
constexpr int N = 1e5;
int in, ia[N];
void sa(){
double t = in;
UP(i, 0, 3e6){
t *= 0.99999;
int x = rng() % in;
int y = (int)(x + unif(rng)*t) % in;
if(x == y) y = (y + 1)%in;
if(x > y) std::swap(x, y);
if(std::exp((ia[x]-ia[y])/t) > unif(rng)){
std::swap(ia[x], ia[y]);
}
}
}
void work(){
cin >> in;
UP(i, 0, in) cin >> ia[i];
sa();
UP(i, 0, in) cout << ia[i] << ' ';
}
} // {}}}
int main(){m::work(); return 0;}此时能在模板题中拿到
闲来无事的读者或许能用更高级的手段优化猴排，争取能 AC 模板题（？