题解 P2190 【小Z的车厢】

oistr · 2019-06-22 21:38:25 · 题解

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{锕}了。