【Route】

【问题描述】

一条直线上有n个人在走。

有三个值来描述第i个人的行为:t[i],s[i],f[i],分别表示他出发的时间,他的起点位置和终点位置。假设每个人走的一样快,他们每个单位时间只会朝目的地走一个单位的距离。

当两个人相遇的时候,他们相互之间会打招呼。按照常理,两个人之间最多只会打一次招呼。

请算出每个人在他的旅程中要和多少个人打招呼。

(注:当一个人走完了或者还没开始走,那么那人处于消失状态,即经过他也不打招呼,但是追上的瞬间消失要打招呼)

【输入格式】

输入第一行包括一个整数n表示人数。

接下来n行,每行三个整数t[i],s[i],f[i]。

【输出格式】

一行n个整数。第i个整数a[i]表示第i个人总共要和a[i]个人(总人数)打招呼。

【输出样例】

3

1 1 10

5 8 2

9 9 10

【输出样例】

2 1 1

【数据范围】

对30%的输入数据:n≤10

对100%的输入数据:n≤1000,1≤t[i],s[i],f[i]≤1000000,s[i]≠f[i]

大特判题,对于起始时间不相等的两个人把他们起始时间等效到相等时再来判断。

另外,本题也可以通过考虑同向和逆向的情况,可以分别列出简单的一元一次方程,妥善处理边界情况,复杂度O(n²)

下面是我蒟蒻的代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*