题解 CF639E 【Bear and Paradox】

· · 题解

标签: 贪心, 二分答案.

Part 1

首先我们需要知道一个最优顺序有什么样的性质.

实际上是按 \frac{p_i}{t_i} 递减的顺序就可以的到最优顺序. 考虑反证, 若(排序后)存在一个 i 使得 \frac{p_i}{t_i}<\frac{p_{i+1}}{t_{i+1}}, 则这两题的得分为 s_1=p_i(1-\frac{c(T'+t_i)}{T})+p_{i+1}(1-\frac{c(T'+t_{i}+t_{i+1})}{T}) , 其中 T'=\sum_{j=1}^{i-1}t_i.

我们交换这两道题的顺序, 其他题目得分显然不发生变化, 而这两题的得分变为 s_2=p_{i+1}(1-\frac{c(T'+t_{i+1})}{T})+p_{i}(1-\frac{c(T'+t_{i}+t_{i+1})}{T}) , 那么 s_1-s_2=p_i\frac{ct_{i+1}}{T}-p_{i+1}\frac{ct_i}{T}=\frac{c}{T}(p_it_{i+1}-p_{i+1}t_i), 由 \frac{p_i}{t_i}<\frac{p_{i+1}}{t_{i+1}} 可知 s1-s2<0 , 矛盾.

Part 2

有了 Part 1 的结论后, 我们就可以处理出每个问题的最早完成时间和最晚完成时间. 然后二分一个 c , 判断每个问题 i 存不存在一个 p_j<p_i 的 j , 使得 i 最晚完成的得分小于 j 最早完成的得分, 如果存在就不合法, 否则就合法.

时间复杂度 \mathcal O(n(\log eps+\log n)).

#include <bits/stdc++.h>
using namespace std;
int read();

int n;
int st[200005], top;
long long T;
struct P {
    long long p, t, tmin, tmax, sum;
    int fp;
} p[200005];

bool cmppdivt(P a, P b) { return a.p * b.t > b.p * a.t; }
bool cmpp(P a, P b) { return a.p < b.p; }
bool check(double x) {
    double mx = 0, tmx = 0;
    for (int i = 1; i <= n; ++i) {
        if (p[i].p != p[i - 1].p) mx = tmx;
        if ((1 - x * p[i].tmax / T) * p[i].p < mx) return 0;
        tmx = max(tmx, (1 - x * p[i].tmin / T) * p[i].p);
    }
    return 1;
}

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) st[i] = p[i].p = read();
    for (int i = 1; i <= n; ++i) T += (p[i].t = read());

    sort(st + 1, st + 1 + n), top = unique(st + 1, st + 1 + n) - st - 1;
    for (int i = 1; i <= n; ++i)
        p[i].fp = lower_bound(st + 1, st + top + 1, p[i].p) - st;
    sort(p + 1, p + 1 + n, cmppdivt);
    for (int i = 1; i <= n; ++i) p[i].sum = p[i - 1].sum + p[i].t;

    for (int i = 1, j; i <= n; i = j + 1) {
        j = i;
        while (j < n && p[j + 1].p * p[i].t == p[i].p * p[j + 1].t) ++j;
        for (int k = i; k <= j; ++k)
            p[k].tmin = p[i - 1].sum + p[k].t, p[k].tmax = p[j].sum;
    }
    sort(p + 1, p + 1 + n, cmpp);
    double l = 0, r = 1, mid;
    while (r - l > 1e-6) check(mid = (l + r) / 2) ? l = mid : r = mid;
    printf("%.8lf", l);
    return 0;
}
const int _SIZE = 1 << 22;
char ibuf[_SIZE], *iS = ibuf, *iT = ibuf;
#define gc                                                         \
    (iS == iT ? iT = ((iS = ibuf) + fread(ibuf, 1, _SIZE, stdin)), \
     (iS == iT ? EOF : *iS++) : *iS++)
int read() {
    int x = 0, f = 1;
    char c = gc;
    while (!isdigit(c)) f = (c == '-') ? -1 : f, c = gc;
    while (isdigit(c)) x = x * 10 + c - '0', c = gc;
    return x * f;
}