题解：P10701 [SNCPC2024] 致命公司

SUNCHAOYI · 2024-07-06 19:12:01 · 题解

看完题目后盲猜二分答案（）。

题目的难点显然是如何分配凝视的时间于不同的通道，以及如何在一次凝视时将通道内的子弹进行标记。

二分时刻 t，对于所有的子弹，有以下情况：

• 在 t 时刻，该子弹仍未出现，忽略该子弹。
• 从子弹出现到 t 时刻，不需要额外再使用凝视，忽略该子弹。
• 从子弹出现到 t 时刻，需要额外使用凝视，计算并标记。当然，需要先判断所剩的时间能否满足条件。

那么对于第一个难点，可以对子弹出现的时间进行排序，为了使得凝视不会产生后效性，我们按照时间进行降序，依次考虑子弹所在通道所需的凝视时间。对于第二个难点，只需再用一个数组记录通道已用的凝视的时间即可。

特别地，当所有子弹都在同一个通道时，永远都不会受到伤害，特判即可。

最后时间复杂度 O(n \log n)。最终代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int MAX = 5e5 + 5;
const int MOD = 1e9 + 7;
inline ll read ();
struct node
{
    ll t,x,y;
} s[MAX];
ll tot,n,m,k,l = 0,r = INF,ans,ex[MAX],st[MAX]; 
bool cmp (node xx,node yy);
ll check (ll ti);
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    n = read ();m = read ();k = read ();
    for (int i = 1;i <= m;++i) 
    {
        s[i].t = read ();s[i].x = read ();s[i].y = read ();
        if (!ex[s[i].x]) ex[s[i].x] = 1,++tot;
    }
    sort (s + 1,s + 1 + m,cmp);//按照时间降序排序
    if (tot == 1) {puts ("-1");return 0;}//特判
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        if (check (mid)) ans = mid,l = mid + 1;
        else r = mid - 1;
    }
    printf ("%lld\n",ans);
    return 0;
}
inline ll read ()
{
    ll s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
bool cmp (node xx,node yy) {return (xx.t == yy.t) ? xx.y < yy.y : xx.t > yy.t;}//时间晚的优先 
ll check (ll ti)
{
    ll ret = ti;//从 ti 开始消耗用于凝视 
    for (int i = 1;i <= n;++i) st[i] = 0;//每个通道被凝视的次数 
    for (int i = 1;i <= m;++i)
    {
        if (ti < s[i].t) continue;//该子弹还未出现 
        ll tmp = (s[i].y - 1) / k + 1 + st[s[i].x] + s[i].t - 1;//到达时的时间 
        if (tmp > ti) continue;//子弹在 ti 时无法达到   
        tmp = ti - tmp + 1;//需要凝视的时间 
        if (ret - tmp + 1 < s[i].t) return 0;//剩余时间无法处理 
        ret -= tmp;st[s[i].x] += tmp;//进行标记
    }
    return 1;
}