P2123 皇后游戏题解

· · 题解

哈哈哈哈哈，我中了！

也许是第一个退火过的？

感觉有点唐。

开始我把答案的变化率和降温系数搞混了，然后一直卡在 95 分。

这就是为什么那一页都是我的提交。

然后改改系数过了。（亲测三次，都过了）

具体实现就是每次退火开始的时候排一下序，然后正常退火即可。

接下来给出退火代码：

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define fd(i,a,b) for(int i=(a);i<=(b);i=-~i)
#define bd(i,a,b) for(int i=(a);i>=(b);i=~-i)
#define db(x) cout<<"DEBUG "<<#x<<" = "<<x<<endl;
#define endl '\n'
using namespace std;

//#define SIZE (1<<20)
//char In[SIZE],Out[SIZE],*p1=In,*p2=In,*p3=Out;
//#define getchar() (p1==p2&&(p2=(p1=In)+fread(In,1,SIZE,stdin),p1==p2)?EOF:*p1++)
template<typename _T=int>
inline _T read()
{
    _T x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
    return x*f;
}

const int N=1e5+509,M=1e5+509,mod=998244353;
const double st=1e18,ed=1,delta=0.1,tim=0.9;
mt19937 rnd(time(0));

int n,ans;
struct node{int a,b;}t[N];

inline bool operator<(node x,node y)
{
    return min(x.a,y.b)<min(x.b,y.a);
}

inline void init()
{
    n=read();
    fd(i,1,n) t[i].a=read(),t[i].b=read();
    sort(t+1,t+n+1);
}

inline int calc()
{
    int sum=0,res=0;
    fd(i,1,n) sum+=t[i].a,res=max(res,sum)+t[i].b;
    return res;
}

void SA()
{
    double _t=st;
    sort(t+1,t+n+1);
    while(_t>ed)
    {
        int x=rnd()%n+1,y=rnd()%n+1;
        swap(t[x],t[y]);
        int res=calc(),Delta=res-ans;
        if(Delta<0) ans=res;
        else if(exp((double)-Delta/_t)<=((double)rnd()/RAND_MAX))
            swap(t[x],t[y]);
        _t*=delta;
    }
}

inline void Main()
{
    init();
    ans=calc();
    fd(i,1,50) SA();
    printf("%lld\n",ans);
}

signed main()
{
//#define FJ
#ifdef FJ
    freopen("doubt.in","r",stdin);
    freopen("doubt.out","w",stdout);
#else
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
#endif
//#define io
#ifdef io
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#endif

    int T=read();
    while(T--) Main();

    return 0;
}