深谈模拟着火/模拟火灾

rabbitohh · 2023-10-17 20:52:44 · 个人记录

先看一道例题：
P1001 A+B Problem
聪明的读者可能已经发现，本题可以使用模拟火退、模拟治水等方法通过，在这里，本文将使用一种新的方法解决本题：模拟着火，又名模拟火灾。

读入 a、b，没什么好说的。

以如下方法建立 t 数组，方法如下：对于每一个元素，在 a 和 b 中随机选择一个。

开始模拟着火过程，在模拟的每一轮，随机烧掉 t 数组的一部分元素，且温度越高，概率越大，随后降低温度。

火灾后，统计答案，将 t 数组未被烧掉的元素中最大值与最小值相加即可。

#include<cstdio>
#include<iostream>
#include<random>
#include<ctime>
#define int long long
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
int t[N];
mt19937 rnd(time(0));
int rand(int l,int r)
{
    return rnd()%(r-l+1)+l;
}
void fire(int &x,int T)
{
    if(rand(0,1e9)<T)
    {
        x=inf;//烧掉x
    }
}
signed main()
{
    int a,b;
    cin>>a>>b;
    int n=1e5;
    for(int i=1;i<=n;i++)
    {
        if(rand(0,1)==0) t[i]=a;
        else t[i]=b;
        //cout<<t[i]<<'\n';
    }
    int T=3e8;
    while(T)
    {
        for(int i=1;i<=n;i++)
        {
            fire(t[i],T);
            //cout<<t[i]<<'\n';
        }
        T*=0.95;
    }
    int A=-inf,B=inf;
    for(int i=1;i<=n;i++)
    {
        if(t[i]!=inf)
        {
            A=max(A,t[i]);
            B=min(B,t[i]);
        }
    }
    cout<<A+B;
    return 0;
} 

另：本做法在未卡时的情况下，仅调参就达成了本题最劣解：10000ms，link