TIOJ 2064：排水系統管理

TIOJ 2064：排水系統管理

題目大意：有一個高度為 $H$ 的水桶，每秒高度下降的量為低於此高度且開啟的閘門數量，給你每個閘門開啟、關閉的時間還有高度，問你要經過多少時間水的高度才會到達 $0$，或是永遠無法達成。

解法：將每個閘門的開關案時間由小到大排序好，紀錄每個可能到達的高度，由大到小排序好，並記錄每個高度的閘門有多少個是開著的，只要水位低於此高度，就將總開啟量扣掉這個高度的開啟量，之後模擬一遍就好了。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define TIOJQQ ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;
const double INF = 9e18;

int N;
double H, T;
vector<int> height (1, 0);
unordered_map<int, int> mp; // height, count
vector<tuple<int, int, int>> times; // time, height, open

void solve() {
    cin >> N >> H;
    FOR (i, 1, N) {
        int l, r, d;
        cin >> l >> r >> d;
        height.pb (d);
        times.pb (l, d, 1);
        if (r != -1) times.pb (r, d, -1);
    }

    sort (times.begin(), times.end());
    sort (height.begin(), height.end(), greater());
    height.erase (unique (height.begin(), height.end()), height.end());

    int p = 0, tot = 0;
    for (int to : height) {
        while (p < times.size()) {
            auto [t, h, delta] = times[p];
            if (h >= H) {p++; continue;}
            double t1 = tot == 0 ? INF : (H - to) / tot;
            double t2 = t - T;
            if (t1 <= t2) break;
            H -= tot * t2;
            T += t2;
            mp[h] += delta;
            tot += delta;
            p++;
        }
        if (H != to && tot == 0) {cout << "-1\n"; return;}
        T += (H - to) / tot;
        H = to;
        tot -= mp[to];
    }
    cout << fixed << setprecision (15) << T << '\n';
}

int main() {
    TIOJQQ;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！