40 pts,求调参数或者降低常数(各种玄学方法都可)。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <cmath>
using namespace std;
const int N = 210;
int n, m, w[N], v[N];
double res = -0x3f3f3f3f;
double calc()
{
int a = 0, b = 0;
for (int i = 1; i <= m; i ++ )
a += w[i], b += v[i];
double tot = (double)a / b;
if (tot > res) res = tot;
return tot;
}
void simulate_anneal()
{
for (double t = 1e6; t >= 1e-4; t *= 0.99)
{
double x = calc();
int a = rand() % m + 1, b = rand() % n + 1;
swap(w[a], w[b]), swap(v[a], v[b]);
double y = calc();
double delta = y - x;
if (exp(-delta / t) < rand() / RAND_MAX)
swap(w[a], w[b]), swap(v[a], v[b]);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
scanf("%d", &w[i]);
for (int i = 1; i <= n; i ++ )
scanf("%d", &v[i]);
while (clock() / CLOCKS_PER_SEC <= 0.9) simulate_anneal();
printf("%.3lf\n", res);
return 0;
}