Loading...

洛谷P3878 [TJOI2010]分金币

check评论:0 条 remove_red_eye浏览量:404 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-12-02

模拟退火好题qwq

我们用模拟退火来随机交换我们选择的数字

多来几次,寻找最优解就行了

#include <bits/stdc++.h>
using namespace std;
int a[60],n;
int ans;
int check()
{
    int myans=0;
    for(int i=1;i<=n;i++)
    {
        if(i<=(n+1)/2)
        {
            myans+=a[i];
        }
        else
        {
            myans-=a[i];
        }
    }
    return abs(myans);
}
void SA()
{
    double temp=2500.0;
    while(temp>1)
    {
        int l=rand()%((n+1)/2)+1;
        int r=rand()%((n+1)/2)+((n+1)/2);
        if(r>n) continue;
        swap(a[l],a[r]);
        int perans=check();
        int task=ans-perans;
        if(task>0)
        {
            ans=perans;
        }
        else if(exp((double)((double)task/temp))*RAND_MAX<=rand())
        {
            swap(a[l],a[r]);
        }
        temp*=0.995;
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ans=(int)1e9;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=100;i++)
        {
            SA();
        }
        printf("%d\n",ans);
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名