什么毒瘤...
解：n = 1的，发现就是一个二次函数，解出来一个v的取值范围，选最大的即可。
n = 2的，猜测可以三分。于是先二分给第一段路多少能量，然后用上面的方法求第二段路的最短时间。注意剩余能量不足跑完第二段路的时候，返回INF。
正解是啥拉格朗日乘子法，完全搞不倒...
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/ #include <bits/stdc++.h> const int N = ; double k[N], s[N], vv[N], E;
int n; namespace n1 {
inline void solve() {
double v = vv[] + sqrt(E / s[] / k[]);
printf("%.10f\n", s[] / v);
return;
}
} namespace n2 { inline double cal(double v) {
double ans = s[] / v;
double delta = k[] * s[] * (vv[] - v) * (vv[] - v);
//printf("E - delta = %.10f \n", E - delta);
double v2 = vv[] + sqrt((E - delta) / s[] / k[]);
if(v2 < ) return 1e14;
//printf("v2 %.10f = %.10f + sqrt(%.10f / %.10f / %.10f) \n", v2, vv[2], E - delta, s[2], k[2]);
//printf(" = %.10f + %.10f \n", vv[2], sqrt((E - delta) / s[2] / k[2]));
//printf("cal %.10f -> %.10f + %.10f / %.10f \n", v, ans, s[2], v2);
return ans + s[] / v2;
} inline void solve() { double l = , r = vv[] + sqrt(E / s[] / k[]);
for(int i = ; i <= ; i++) {
double mid = (l + r) / ;
//printf("l = %.10f r = %.10f \n", l, r);
double ml = mid - (r - l) / , mr = mid + (r - l) / ;
double vl = cal(ml), vr = cal(mr);
if(vl > vr) {
l = ml;
}
else {
r = mr;
}
}
printf("%.10f\n", cal(r));
return;
}
} int main() {
scanf("%d%lf", &n, &E);
for(int i = ; i <= n; i++) {
scanf("%lf%lf%lf", &s[i], &k[i], &vv[i]);
} if(n == ) {
n1::solve();
return ;
} if(n == ) {
n2::solve();
return ;
} return ;
}
40分代码
学习了一波模拟退火，突然发现这道题可能比较适合乱搞？于是开始疯狂调参最后成功在LOJ和洛谷上A掉了...
考虑如何随机化得出解。我们随机每条路的能量分配即可。
风速为负的每条路有一个能量下限。在此基础上我们把多出来的能量作为*能量来进行分配。
初始解就是把*能量均分...之后我们每次随机出两条路a和b，把a的若干能量给b。这里我给的能量是min(a的能量，T * c) * Rand(0, 1)
这里的c是一个参数。于是我们做到了让调整量随着温度的降低而变小。
然后瞎调一波，从0分优化到了100分......中间有很多脑洞大开改参数的过程...
最好玩的是LOJ的AC代码在洛谷上95分，洛谷的AC代码在LOJ上90分...
// luogu-judger-enable-o2
#include <bits/stdc++.h> const int N = , INF = 0x3f3f3f3f; double k[N], s[N], vv[N], E;
int n; namespace n1 {
inline void solve() {
double v = vv[] + sqrt(E / s[] / k[]);
printf("%.10f\n", s[] / v);
return;
}
} namespace n2 { inline double cal(double v) {
double ans = s[] / v;
double delta = k[] * s[] * (vv[] - v) * (vv[] - v);
double v2 = vv[] + sqrt((E - delta) / s[] / k[]);
if(v2 < ) return 1e14;
return ans + s[] / v2;
} inline void solve() { double l = , r = vv[] + sqrt(E / s[] / k[]);
for(int i = ; i <= ; i++) {
double mid = (l + r) / ;
//printf("l = %.10f r = %.10f \n", l, r);
double ml = mid - (r - l) / , mr = mid + (r - l) / ;
double vl = cal(ml), vr = cal(mr);
if(vl > vr) {
l = ml;
}
else {
r = mr;
}
}
printf("%.10f\n", cal(r));
return;
}
} namespace Fire {
const double eps = 1e-;
double T = , dT = 0.999992;
double nowE[N], temp[N], lm[N];
int test[N]; inline int rd(int l, int r) {
return rand() % (r - l + ) + l;
} inline double Rand() {
return 1.0 * rand() / RAND_MAX;
} inline double calv(int i, double e) {
return vv[i] + sqrt(e / k[i] / s[i]);
} inline double calt(int i, double e) {
return s[i] / (vv[i] + sqrt(e / k[i] / s[i]));
} inline double init() {
for(int i = ; i <= n; i++) {
if(vv[i] < -eps) {
lm[i] = k[i] * s[i] * vv[i] * vv[i];
E -= lm[i];
}
}
double dt = E / n, ans = ;
for(int i = ; i <= n; i++) {
nowE[i] = dt;
ans += calt(i, lm[i] + nowE[i]);
}
return ans;
} inline void solve() {
double ans, fin = 1e14;
srand();
for(int A = ; A <= ; A++) {
ans = init();
fin = std::min(ans, fin);
while(T > eps) {
/// Random a new solution
int a = rd(, n), b = rd(, n);
while(a == b) {
a = rd(, n), b = rd(, n);
}
double deltaE = std::min((long double)nowE[a], (long double)T * 1e8) * Rand();
temp[a] = nowE[a] - deltaE;
temp[b] = nowE[b] + deltaE; double New = ans - calt(a, lm[a] + nowE[a]) - calt(b, lm[b] + nowE[b])
+ calt(a, lm[a] + temp[a]) + calt(b, lm[b] + temp[b]); fin = std::min(fin, New);
if(New < ans || Rand() < exp((ans - New) / T)) {
ans = New;
nowE[a] = temp[a];
nowE[b] = temp[b];
}
T = T * dT;
}
}
printf("%.10f\n", fin);
return;
}
} int main() {
scanf("%d%lf", &n, &E);
for(int i = ; i <= n; i++) {
scanf("%lf%lf%lf", &s[i], &k[i], &vv[i]);
} if(n == ) {
n1::solve();
return ;
} if(n == ) {
n2::solve();
return ;
} Fire::solve();
return ;
}
洛谷AC代码
#include <bits/stdc++.h> const int N = , INF = 0x3f3f3f3f; double k[N], s[N], vv[N], E;
int n; namespace n1 {
inline void solve() {
double v = vv[] + sqrt(E / s[] / k[]);
printf("%.10f\n", s[] / v);
return;
}
} namespace n2 { inline double cal(double v) {
double ans = s[] / v;
double delta = k[] * s[] * (vv[] - v) * (vv[] - v);
double v2 = vv[] + sqrt((E - delta) / s[] / k[]);
if(v2 < ) return 1e14;
return ans + s[] / v2;
} inline void solve() { double l = , r = vv[] + sqrt(E / s[] / k[]);
for(int i = ; i <= ; i++) {
double mid = (l + r) / ;
//printf("l = %.10f r = %.10f \n", l, r);
double ml = mid - (r - l) / , mr = mid + (r - l) / ;
double vl = cal(ml), vr = cal(mr);
if(vl > vr) {
l = ml;
}
else {
r = mr;
}
}
printf("%.10f\n", cal(r));
return;
}
} namespace Fire {
const double eps = 1e-;
double T = , dT = 0.99999;
double nowE[N], temp[N], lm[N];
int test[N]; inline int rd(int l, int r) {
return rand() % (r - l + ) + l;
} inline double Rand() {
return 1.0 * rand() / RAND_MAX;
} inline double calv(int i, double e) {
return vv[i] + sqrt(e / k[i] / s[i]);
} inline double calt(int i, double e) {
return s[i] / (vv[i] + sqrt(e / k[i] / s[i]));
} inline double init() {
for(int i = ; i <= n; i++) {
if(vv[i] < -eps) {
lm[i] = k[i] * s[i] * vv[i] * vv[i];
E -= lm[i];
}
}
double dt = E / n, ans = ;
for(int i = ; i <= n; i++) {
nowE[i] = dt;
ans += calt(i, lm[i] + nowE[i]);
}
return ans;
} inline void solve() {
double ans, fin = 1e14;
srand();
for(int A = ; A <= ; A++) {
ans = init();
fin = std::min(ans, fin);
while(T > eps) {
/// Random a new solution
int a = rd(, n), b = rd(, n);
while(a == b) {
a = rd(, n), b = rd(, n);
}
double deltaE = std::min((long double)nowE[a], (long double)T * 1e11) * Rand();
temp[a] = nowE[a] - deltaE;
temp[b] = nowE[b] + deltaE; double New = ans - calt(a, lm[a] + nowE[a]) - calt(b, lm[b] + nowE[b])
+ calt(a, lm[a] + temp[a]) + calt(b, lm[b] + temp[b]); fin = std::min(fin, New);
if(New < ans || Rand() < exp((ans - New) / T)) {
ans = New;
nowE[a] = temp[a];
nowE[b] = temp[b];
}
T = T * dT;
}
}
printf("%.8f\n", fin);
return;
}
} int main() {
scanf("%d%lf", &n, &E);
for(int i = ; i <= n; i++) {
scanf("%lf%lf%lf", &s[i], &k[i], &vv[i]);
} if(n == ) {
n1::solve();
return ;
} if(n == ) {
n2::solve();
return ;
} Fire::solve();
return ;
}
LOJAC代码
调参心得：△T越接近1，就越慢，同时效果越好。初始温度太大可能会超时...