求助斜率优化
查看原帖
求助斜率优化
236416
_stOrz_楼主2023/9/18 09:11
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e6 + 5;

int n, L;
double X[N], Y[N], K[N];
int s[N], cg[N], sc[N], f[N], q[N];

struct node {
  int a, c;
} g[N];

double slope (int x, int y) {
  return 1.0 * (Y[x] - Y[y]) / (X[x] - X[y]); 
}

signed main () {
 // freopen ("in.in", "r", stdin);
 // freopen ("out.out", "w", stdout);
  cin >> n >> L;
  for (int i = 1; i <= n; i ++)
    cin >> g[i].a >> g[i].c;
  sort (g + 1, g + n + 1, [] (node x, node y) { return x.a < y.a; });
  for (int i = 1; i <= n; i ++) {
    s[i] = s[i - 1] + g[i].a;
    sc[i] = sc[i - 1] + g[i].c;
    cg[i] = cg[i - 1] + g[i].a * g[i].c;
  }
  
  for (int i = 1; i <= n; i ++)
    X[i] = sc[i], K[i] = g[i].a;
  Y[0] = 0;

  int l = 1, r = 1; q[1] = 0;
  for (int i = 1; i <= n; i ++) {
    while (l < r and slope (q[l], q[l + 1]) < K[i]) ++ l;
    int j = q[l]; //cout << j << " ";
    f[i] = Y[j] - K[i] * X[j] - cg[i] + sc[i] * g[i].a + L;
    Y[i] = f[i] + cg[i];
    while (l < r and slope (q[r - 1], q[r]) >= slope (q[r - 1], i)) -- r;
    q[++ r] = i;
  }
  
  cout << f[n] << "\n";
}

test1~10 全挂了

2023/9/18 09:11
加载中...