人品退火诚不欺我

我是在比赛前一周才得知我有机会参加省选的，而在那之前，由于学业繁忙，我已经一个多月没有上机练习了。

本蒟蒻实力与省选比赛水平严重不匹配，但赛场上也能轻松推出T1的m方算法，即首尾端暴力枚举：

void work(int l,int r){
	int minn,maxx;
	minn=inf;maxx=0;
	for(int i=1;i<=l;++i){
		minn=min(minn,b[i]);
		maxx=max(maxx,b[i]);
	}
	for(int i=n;i>=r;--i){
		minn=min(minn,b[i]);
		maxx=max(maxx,b[i]);
	}
	if(l!=n)minn=min(minn,a[l+1]);
	if(r!=1)maxx=max(maxx,a[r-1]);
	ans=min(ans,maxx-minn);
}

main(){
	for(l=1;l<=n;++l)
	if(a[l]>b[l]){
		--l;
		break;
	}
	for(r=n;r>=1;--r)
	if(a[r]<b[r]){
		++r;
		break;
	}
	ans=a[n]-a[1];
	if(!(!l&&r>n)){
		for(int i=1;i<=l;++i)
		for(int j=n;j>=r;--j)work(i,j);
	}
	printf("%d\n",ans);
}

但问题也是显而易见的，这样程序顶天也只有60pts啊喂 虽然这样我也觉得不亏了

在一番激烈的思想斗争之后，我决定试试人品，多花了二十多分钟码了一个退火，于是就有了以下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=2e6,inf=0x7fffffff-1;
const double T=1e4;
const double L=0.99;//退火系数 
const double F=1e-13;//末温 
int n,m,a[N],b[N],l,r,ans;
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+(ch^48);
		ch=getchar();
	}
	x*=f;
}
void work(int l,int r){
	int minn,maxx;
	minn=inf;maxx=0;
	for(int i=1;i<=l;++i){
		minn=min(minn,b[i]);
		maxx=max(maxx,b[i]);
	}
	for(int i=n;i>=r;--i){
		minn=min(minn,b[i]);
		maxx=max(maxx,b[i]);
	}
	if(l!=n)minn=min(minn,a[l+1]);
	if(r!=1)maxx=max(maxx,a[r-1]);
	ans=min(ans,maxx-minn);
}
int work_ans(int x,int y){
	if(x<0||x>l||y<r||y>n+1)return inf;
	int minn,maxx;
	minn=inf;maxx=0;
	for(int i=1;i<=x;++i){
		minn=min(minn,b[i]);
		maxx=max(maxx,b[i]);
	}
	for(int i=n;i>=y;--i){
		minn=min(minn,b[i]);
		maxx=max(maxx,b[i]);
	}
	if(x!=n)minn=min(minn,a[x+1]);
	if(y!=1)maxx=max(maxx,a[y-1]);
	return maxx-minn;
}
void SA(){
	double temp=T;
	int x,y,nx,ny,res;
	x=0;y=n+1;
	while(temp>F){
		nx=x+(int)(2*rand()-RAND_MAX)*temp;
		ny=y+(int)(2*rand()-RAND_MAX)*temp;
		res=work_ans(nx,ny);
		if(ans-res>0){
			ans=res;
			x=nx;
			y=ny;
		}
		else if(exp(-(ans-res)/temp)>rand()/RAND_MAX){//(exp(ans-res)*temp>rand()/RAND_MAX) 
			x=nx;
			y=ny;
		}
		temp*=L;
	}
}
int main(){
	freopen("card.in","r",stdin);
	freopen("card.out","w",stdout);
	srand((unsigned int)time(0));srand(rand());
	read(n);read(m);
	for(int i=1;i<=n;++i)read(a[i]);
	for(int i=1;i<=n;++i)read(b[i]);
	for(l=1;l<=n;++l)
	if(a[l]>b[l]){
		--l;
		break;
	}
	for(r=n;r>=1;--r)
	if(a[r]<b[r]){
		++r;
		break;
	}
	ans=a[n]-a[1];
	if(!(!l&&r>n)){
		/*if(n<=1e3)
		for(int i=1;i<=l;++i)
		for(int j=n;j>=r;--j)work(i,j);
		else */
		//以上是O(m^2)算法 
		while(clock()<600)SA();
	}
	printf("%d\n",ans);
	return 0;
}

我没注意到的是，在决定暴枚还是退火的if分支里，我把测试点5~6给排开了，这就意味着把20分的稳定暴力让给了人品退火 （悲）

还有一点比较有意思的是玄学Mertropolis准则公式。套用标准公式：

exp(-(ans-res)/temp)>rand()/RAND_MAX

的话我只能过样例1

但接下来我又意会创造出了一套新公式，即：

(exp(ans-res)*temp>rand()/RAND_MAX)

奇特的是，用上这套公式的话样例1、2稳过，但样例3每次都能得出不同的结果 甚至每次都比最优答案还要小

就结果来说，我应该是白白耗掉了20分暴力，打了一个高级一点的rand()罢了

如果有dalao能对这份代码提供提供意见，我会非常感谢~