自动搬运

查看原文

来自洛谷，原作者为

	SUNCHAOYI 报名个人赛 https://www.luogu.com.cn/contest/44296

搬运于2025-08-24 23:00:24，当前版本为作者最后更新于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;
}