题解：P10701 [SNCPC2024] 致命公司
看完题目后盲猜二分答案（）。
题目的难点显然是如何分配凝视的时间于不同的通道，以及如何在一次凝视时将通道内的子弹进行标记。
二分时刻 $t$，对于所有的子弹，有以下情况：
- 在 $t$ 时刻，该子弹仍未出现，忽略该子弹。
- 从子弹出现到 $t$ 时刻，不需要额外再使用凝视，忽略该子弹。
- 从子弹出现到 $t$ 时刻，需要额外使用凝视，计算并标记。当然，需要先判断所剩的时间能否满足条件。
那么对于第一个难点，可以对子弹出现的时间进行排序，为了使得凝视不会产生后效性，我们按照时间进行降序，依次考虑子弹所在通道所需的凝视时间。对于第二个难点，只需再用一个数组记录通道已用的凝视的时间即可。
特别地，当所有子弹都在同一个通道时，永远都不会受到伤害，特判即可。
最后时间复杂度 $O(n \log n)$。最终代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #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 ()
{
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;
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;
tmp = ti - tmp + 1;
if (ret - tmp + 1 < s[i].t) return 0;
ret -= tmp;st[s[i].x] += tmp;
}
return 1;
}
|
