题解：AT_arc128_c [ARC128C] Max Dot

_LiM · 2025-07-22 17:20:38 · 题解

不妨设 x_i = \sum_{j=1}^{n} d_j，那么问题可以改写成线性规划形式

maximize a[1] * d[1] + a[2] * d[2] + ... + a[n] * d[n]
such that
d[i] >= 0, i = 1, 2, ..., n
d[1] + d[2] + ... + d[n] <= m
n*d[1] + (n-1)*d[2] + ... + d[n] <= s

把问题对偶可以得到如下对偶线性规划

minimize mx[1] + sx[2]
such that
x[1], x[2] >= 0
x[1] + nx[2] >= a[1]
x[1] + (n-1)x[2] >= a[2]
...
x[1] + 1x[2] >= a[n]

这个线性规划问题若确定 x[1] 则最优解是很好算的，让这个最优解为 f(x[1]). 观察到 f(x) 对 x 单谷，三分即可。

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 5005;
int n, m, s;
ll a[N];
int p[N];
double d[N];

double val (double X) {
  double ans = 0;
  for (int i = 1; i <= n; ++i) {
    ans = max(ans, (double)(a[i] - X) / (n - i + 1));
  }
  return s * ans + m * X;
}

/*
*/
int main() {
  cin >> n >> m >> s;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    p[i] = i;
  }

  for (int i = n; i >= 1; --i)
    a[i] += a[i + 1];

  double l = 0, r = 1e10, ans = 0;
  while (r - l > 1e-6) {
    double fr = (l + 2 * r) / 3, fl = (2 * l + r) / 3;
    if (val(fl) < val(fr)) r = fr;
    else l = fl;
  }
  cout << fixed << setprecision(12) << val(l);
  return 0;
}