模拟退火模板

#include <bits/stdc++.h>

using ll = long long;

double calc() {
    
    // ans = std::min(ans, res);
    // ans = std::max(ans, res);
}

void SA() {
    std::random_shuffle(a, a + n);  //随机排列方案
    for (double t = 1e6; t > 1e-6; t *= 0.99) {  //模拟退火的参数 起始温度，终止温度，温度衰减参数
        int x = rand() % n, y = rand() % n; //随机两个点
        double now = calc();//交换前
        std::swap(a[x], a[y]); 
        double ne = calc(); //交换后
        double dif = ne - now; //差值
         //exp(-dif / t) > (double)rand() / RAND_MAX 新的点更优就一定选，否则有概率选，差值越小越容易选
        if (exp(-dif / t) < (double)rand() / RAND_MAX) {  
            std::swap(a[x], a[y]); //交换回去，也就是不选新的点
        }
    }
}

int main () {    
    std::ios::sync_with_stdio(0); 
    std::cin.tie(0);

    std::cin >> n;
    for (int i = 0; i < n; i ++) {
        std::cin >> a[i];
    }

    for (int i = 0; i < 100; i ++) {  //模拟退火100次
        SA();
    }

    std::cout << ans << "\n";

    return 0;
}