[TIOJ] 1882. pC. 最暖的冬天
題目連結:http://tioj.infor.org/problems/1882
本題是要求一堆二次函數取min疊加起來後的最大值,因為二次函數疊加起來後其實斜率還是有單調性,因此可以三分搜出答案,不過我不太喜歡寫三分搜,因此就寫了個模擬退火(當初是培訓時有人提了這鬼東東ww),研究了一下發現滿有趣的,簡單來說就是隨邊挑個起點,走走看如果比較好就走,如果比較差就用$e^{\Delta y \times t}$ 來判斷是否要走下去(這裡的t指的是步數,原本是用溫度),不過因為本題的斜率有單調性,所以不需要往下(這好像又叫爬山法)。此外我裡面還用了C++的random,發現可調的參數真的變多了,但相對的用起來也沒那麼無腦了XD
本題是要求一堆二次函數取min疊加起來後的最大值,因為二次函數疊加起來後其實斜率還是有單調性,因此可以三分搜出答案,不過我不太喜歡寫三分搜,因此就寫了個模擬退火(當初是培訓時有人提了這鬼東東ww),研究了一下發現滿有趣的,簡單來說就是隨邊挑個起點,走走看如果比較好就走,如果比較差就用$e^{\Delta y \times t}$ 來判斷是否要走下去(這裡的t指的是步數,原本是用溫度),不過因為本題的斜率有單調性,所以不需要往下(這好像又叫爬山法)。此外我裡面還用了C++的random,發現可調的參數真的變多了,但相對的用起來也沒那麼無腦了XD
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
struct wow{
double a,b,c;
};
vector<wow> func;
inline double getY(double x);
int main(){
cin.tie(NULL);ios_base::sync_with_stdio();
default_random_engine rGen;
uniform_real_distribution<double> rForm(-1,1);
auto random = bind(rForm,rGen);
int n;
cin>>n;
func.resize(n);
for(int i=0;i<n;i++) cin>>func[i].a>>func[i].b>>func[i].c;
uniform_real_distribution<double> inipos(0,90);
double x=inipos(rGen);
double y=getY(x);
double pace=90;
const double rate=0.9;
double minPace=1e-7;
while(pace>minPace){
double newX=x+random()*pace;
while(newX<0||newX>90)newX=x+random()*pace;
double newY=getY(newX);
if(newY>y){
x=newX;
y=newY;
}else pace*=rate;
}
cout<<setprecision(6)<<fixed<<x<<endl;
return 0;
}
inline double getY(double x){
double rr;bool flag=1;
for(auto i:func){
double val = i.a*x*x+i.b*x+i.c;
if(flag){
rr=val;
flag=0;
}else rr=min(rr,val);
}
return rr;
}
留言
張貼留言