自动搬运

查看原文

来自洛谷，原作者为

	oistr AFO on 2020/12/10

搬运于2025-08-24 21:34:58，当前版本为作者最后更新于2019-06-22 21:38:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\color{white}\text{洛谷文章编号:139177}$

update:更正了一点，故重新提交

看着各位神仙大显神通，本蒟蒻也来发一篇。

首先有一位大佬用了树状数组啥的，其实根本不用，直接暴力模拟就行了。

其实一开始看到这道题是我还感觉很简单，花了10min就打出了代码:

#include <iostream>
using namespace std;
int on[1000000],off[1000000];//on、off数组分别记录第i站上、下车的人数
int main()
{
	int n,m,x,y,z;//按照题目所述
	cin>>n>>m;
	for(int i=1;i<=m;i++)//循环输入并设置on、off数组
	{
		cin>>x>>y>>z;
		on[x]+=z;
		off[y]+=z;
	}
	int train=0,sum=0;//train存放当前的火车上的人数
	for(int i=1;i<=n;i++)
	{
		train+=on[i];
		train-=off[i];//循环模拟上下车
		sum=max(sum,train);//更新最多时的人数
	}
    //判断并输出所需车厢数
	if(sum%36!=0)
	{
		cout<<sum/36+1<<endl;
	}
	else
	{
		cout<<sum/36<<endl;
	}
	return 0;
}

但是之后发现$\color{red}\text{WAWAWA了。}$

那么原因何在呢？

（憋忘了，$\color{green}\text{这是一道绿题啊。。。}$）（滑稽）

为甚会WA呢？我们再仔细读一读题。

小Z的家乡有一条环形的铁路

x不等于y

这意味着什么？环形铁路，x不等于y，不就是说，，，

x>y

吗

为什么会出现起始站序号大于下车站的序号呢？

我们来看下面的图：

应该很清楚了，按照图中的路线，这个旅客共经过了$3->4->1->2$这些站，实现了$x>y$。

那么，这样的订单怎么记录呢？

我们将其化成直线考虑：

假设有一个订单 $n=5,x=4,y=2,z=1$ 。那么这位乘客坐在火车上经过的站是上图涂了色的站。

也就是这个乘客经过了4、5、1、2四站……

然后是 顿悟时刻:

这不就相当于：这位乘客在第一站上车，第二站下车，再在第四站上车吗？！

所以这就是某巨佬题解中说的他“不知道为什么的玄学语句”

on[1]+=z;

！

综上，改进的代码如下：

#include <iostream>
using namespace std;
int on[1000000],off[1000000];//on、off数组分别记录第i站上、下车的人数
int main()
{
	int n,m,x,y,z;//按照题目所述
	cin>>n>>m;
	for(int i=1;i<=m;i++)//循环输入并设置on、off数组
	{
		cin>>x>>y>>z;
		on[x]+=z;
		off[y]+=z;
       if(x>y)
       {
         on[1]+=z;
       }
	}
	int train=0,sum=0;//train存放当前的火车上的人数
	for(int i=1;i<=n;i++)
	{
		train+=on[i];
		train-=off[i];//循环模拟上下车
		sum=max(sum,train);//更新最多时的人数
	}
    //判断并输出所需车厢数
	if(sum%36!=0)
	{
		cout<<sum/36+1<<endl;
	}
	else
	{
		cout<<sum/36<<endl;
	}
	return 0;
}

这就 $\color{green}\text{锕}$了。