某题模拟退火-蒲公英云

某题模拟退火

为了防止某天忘了默默的屯下来…

参考的skyh的代码而写的（虽然大部分都一样吧….）

网上褪的话：增加十倍的初温与末温比值只会增加约25%的迭代次数，而往0.9…99的后面加个9会增加十倍的运行时间。（t==1000不是跑了1000遍的）

#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
const double cg=0.973;
const int maxn=100005;
int n,h[maxn];
int turn[maxn],x;
ll ans;
inline int abs(int x){return (x^(x>>31))-(x>>31);}
ll check(int pos)//模拟位置通过位置知高度再去算代价
{
for(register int i=1;i<=pos;++i) turn[i]=h[i]+pos-i;
for(register int i=pos+1;i<=n;++i) turn[i]=h[i]+i-pos;
int mid=(1+n)>>1;//奇数个显然，偶数个的话左右两个数选谁代价同因为列式子左右两边的两个数和抵消了该数的贡献
nth_element(turn+1,turn+mid,turn+n+1);
x=turn[mid];
if(xx) x=n-pos+1; //这两个if是把不合法的情况（0）排除正确性是因为当x,它们时我把x换过去不就是换了个离中位数最近的吗。所以是对的
ll cost=0;
for(register int i=1;i<=n;++i) cost+=abs(x-turn[i]);
return cost;
}
inline int read()
{
int t=0; char ch=getchar();
while(ch<’0’||ch>’9’) ch=getchar();
while(ch>=’0’&&ch<=’9’) t=(t<<3)+(t<<1)+(ch^48),ch=getchar(); return t; \} int main() \{ srand(time(0)); n=read(); for(register int i=1;i<=n;++i) h\[i\]=read(); double T=985,dt=1e-5; int tmp,now=(1+n)>>1;
ll turnans,nowans,dta;
nowans=check(now); ans=nowans;
while(T>dt)
{
tmp=now+(2ll*rand()-0x7fffffff)*T*0.000001;//保证rand数的随机摆动性左右摆动，rand出来的可能很大*0.000001
if(T<1.00) tmp=max(tmp,1),tmp=min(tmp,n);//别rand出去 else tmp=(tmp%n+n-1)%n+1;//在确保正数情况下rand一个1-n的数 turnans=check(tmp),dta=turnans-nowans; if(turnansrand()) nowans=turnans,now=tmp;//nowans只是我们用来找最优解的一个东西
if(turnans<ans) ans=turnans;//维护最终结果。
T*=cg;//退火降温
}
printf(“%lld”,ans);
return 0;
}