「题解」CF2037F Ardent Flames

Table of contents

• 题面
• 题解
• 代码

题面

https://www.luogu.com.cn/problem/CF2037F

Too long, didn’t translate

题解

不懂咋 *2100 的。

考虑二分答案 $t$，那么对于每个怪物 $i$ 需要每次至少造成 $\lceil \frac{h_i}{t} \rceil$，那么所在的位置必须在 $[x_i - (m - \lceil \frac{h_i}{t} \rceil), x_i + (m - \lceil \frac{h_i}{t} \rceil)]$ 这个区间里面，于是我们只需要判定是否存在一个点被至少 $k$ 个线段覆盖。

然后我们对所有区间 $[l, r]$，把 $l$ 放进一个队列 $q_+$，$r + 1$ 放进另一个队列 $q_-$，然后把这两个队列排序，每次取出较小的那个并对应加减，如果当前值大于等于 $k$ 说明存在被 $k$ 个线段覆盖的点。

$O(n \log n \log V)$，$V$ 是答案的上界。

代码

#include <bits/stdc++.h>
#include <cstdio>

const int MAX = 1e5 + 5;
typedef long long ll;

const ll INF = 1e9 + 7;
int T;
ll h[MAX], x[MAX];
ll n, k, m;

bool check(ll t)
{
    std::deque <int> p, q; ll cnt = 0, mx = 0;
    for (int i = 1; i <= n; ++i)
    {
        ll dmg = (ll)std::ceil(1.0 * h[i] / t);
        if (dmg > m) { continue; }
        ll len = m - dmg;
        p.push_back(x[i] - len); q.push_back(x[i] + len + 1);
    }
    std::sort(p.begin(), p.end()); std::sort(q.begin(), q.end());
    while (!p.empty() and !q.empty())
    {
        if (p.front() == q.front()) { p.pop_front(); q.pop_front(); }
        else if (p.front() < q.front()) { p.pop_front(); ++cnt; }
        else { q.pop_front(); --cnt; }
        mx = std::max(mx, cnt);
    }
    while (!p.empty()) { p.pop_front(); ++cnt; mx = std::max(mx, cnt); }
    while (!q.empty()) { q.pop_front(); --cnt; }
    return mx >= k;
}


void solve()
{
    scanf("%lld%lld%lld", &n, &m, &k);
    for (int i = 1; i <= n; ++i) { scanf("%lld", &h[i]); }
    for (int i = 1; i <= n; ++i) { scanf("%lld", &x[i]); }
    ll ans = INF; ll l = 1, r = INF;
    while (l <= r)
    {
        ll mid = (l + r) / 2;
        if (check(mid)) { ans = mid; r = mid - 1; }
        else { l = mid + 1; }
    }
    if (ans == INF) { printf("-1\n"); }
    else { printf("%lld\n", ans); }
    
}

int main()
{
    scanf("%d", &T); while (T--) { solve(); }
}