AT2402 [ARC072F] Dam

发布于 2020-11-26  57 次阅读


Link

墙裂推荐的好题

Sol

首先考虑一些特殊的情况.

假如每天流进来的水的温度都是递减的,那么我们肯定希望前面的水多一些,后面的水少一些.

假如每天流进来的水温度都是递增的,那么相当于把递减的情况反过来,也就是选出一段后缀.但是在溢出的时候要用一个双指针来维护一下把一些水给倒掉.

现在来想想正解

有了上面两个特殊情况的启发. 在 t_i > t_{i-1} 的时候我们会让他们尽可能少地混合, 要尽可能地多弄温度为 t_i 的水. 相反就要尽可能多地混合.

所以可以维护一个单调队列, 队列中的每个元素就是一段水混合在一起.

溢出的时候直接把队头一段温度比较小的丢掉即可. 然后把现在的水加进队列. 判一下如果 t_{tail-1} > t_{tail}, 那么这个水会破坏队列的单调性,就把他和 tail-1 的水混在一起就可以了

中途维护一下总热量, 每次除以 L 就是答案了

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double 

const int SIZE = 5e5 + 5;

int n, L;
double t[SIZE], v[SIZE];

struct node {
    int v; double t;
} q[SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

signed main() {
    // freopen("crescendo.in", "r", stdin);
    // freopen("crescendo.out", "w", stdout);
    n = read(), L = read();
    for (int i = 1, ti, vi; i <= n; ++ i) {
        ti = read(), vi = read();
        t[i] = ti * 1.0000, v[i] = vi * 1.0000;
    }
    int head = 1, tail = 0;
    int curV = 0; double curT = 0.00000, ans = 0.0000;
    for (int i = 1; i <= n; ++ i) {
        while (curV + v[i] > L) {
            int del = std::min(q[head].v, curV - (L - (int) v[i]));
            q[head].v -= del, curV -= del; ans -= q[head].t * del;
            if (!q[head].v) ++ head;
        }   
        curV = L, ans += t[i] * v[i];
        ++ tail; q[tail].t = t[i], q[tail].v = v[i];
        while (head < tail && q[tail - 1].t > q[tail].t) {
            q[tail - 1].t =
            ((q[tail - 1].v * q[tail - 1].t) + (q[tail].v * q[tail].t)) / (q[tail - 1].v += q[tail].v);
            -- tail;
        }
        printf("%.7Lf\n", ans / L);
    }
    return 0;
}

学会生存 学会关心