别让猴子发烧了，它需要退烧（大雾

先假设我们不会

O(n\log n)

的排序算法（离散化不算！我不管，离散化就不算！）

（侵权请联系删除。）

我们可以看到上面视频中最后一个排序并没有排完。

那就是大名鼎鼎的猴子排序（都听过吧）。

猴子排序是这样的：

给序列 random_shuffle；
判断序列是否有序；
重复执行直到直到有序。

这真是一个聪明的办法！

其时间复杂度期望是

O(n!\times n)

，适用于

n\le 10

。

所以这个猴子发烧了开始瞎随机。

我们需要给它退烧。

怎么退烧呢？

用退火就好啦！

具体的，每次随机交换两个元素，然后判断是不是更好，更好就直接换，否则有一定概率换。

诶，我们怎么判断是不是更好呢？诶对了，聪明的猴子们肯定想到了逆序对。

我们只需要让逆序对更少，就代表更好，是吧。

所以我们得到的以下代码（再说一遍，离散化不算！！！）：

CPP

// 模拟退火+逆序对优化猴子排序，仅供娱乐
#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;
}

诶这个代码已经很优秀了，在

n=15

的时候正确率达到了

91\%

！

但是。

但是但是。

但是但是但是。

但是这个代码在

n=20

的时候正确率只有

8\%

！

我们需要优化。

诶，通过观察可知，我们求逆序对太慢了，求一次要

n\log n

时间。

这也就意味着退火退不了几次就要退出了。

考虑加速求逆序对。

诶呀然后猴子们找到了这个题。

就把一次求逆序对的时间降为了

\log^2 n

的！

我们就有以下代码（再再再说一遍，离散化不算！！！）：

CPP

// 模拟退火+动态逆序对优化猴子排序，仅供娱乐
#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;
}

~~原谅我抄了这篇题解的代码。（侵权请联系删除）~~

这样在

n=15

的时候正确率有

92\%

~~（好像没高多少）。~~

诶但是在

n=20

的时候正确率居然有

18\%

！

它在我们的模板题中能拿到

20

分的好成绩！

这些猴子现在已经是低烧状态了！

难道我们猴子退不了烧了吗？难道随机化真的止步于此了吗？

~~是的。~~

update on 2025-03-31：

感谢 @x383494 提供的进一步优化：

复杂度瓶颈在于求逆序对。

我们考虑模拟退火的时候交换

a_l,a_r(l<r)

，当且仅当

a_l>a_r

才能减少逆序对，此时一定交换，否则以一定概率交换。

这样我们可以不用求逆序对个数，而是直接在

O(1)

时间内考虑是否减少即可。

这是其本人的代码：

CPP

// 看到 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;}

此时能在模板题中拿到

40

分，真的是太优秀啦！

闲来无事的读者或许能用更高级的手段优化猴排，争取能 AC 模板题（？

别让猴子发烧了，它需要退烧（大雾

文章操作

相关推荐

评论

别让猴子发烧了，它需要退烧（大雾