ZZULIOJ-1530小L玩滚球游戏

发布于 2019-08-14  357 次阅读


问题传送门:

题意:

有 n 个水晶球在轨道上以不同开始位置和速度从近往远的方向滚动,
给出 n 个水晶球的初始位置和速度,
如果两个水晶球在滚动过程中相遇,它们就会融合成一个水晶球,
然后以速度较慢的水晶球的速度继续向前滚动, 
问经过时间t后,轨道上还有多少水晶球。

分析:

把每个水晶球最初所能到达的最远位置记录到 dis[] 中,
然后从后往前遍历,
如果 dis[i-1] 比 dis[i] 大,那么更新 dis[i-1]=dis[i]
并且 ans--
至于为什么要从后往前遍历,而不是从前往后。。
一开始想不明白。
但是忽然想到一个反例,比如dis[]数组是 2  3  1
最后答案应该是 1 ,
3 和 1 合并之后也变成 1, 然后再和 2 合并。
但是从前往后遍历是错的。
啊啊啊啊啊啊!!!!!

代码:

#include <iostream>
 
using namespace std;
 
typedef long long LL;
const int MAXN = 1e5+10;
 
LL dis[MAXN];
 
int main()
{
    LL n, t, x, v, ans;
    cin >> n >> t;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> v;
        dis[i] = v*t + x; 
    }
 
    ans = n;
    for (int i = n-1; i > 0; i--)
    {
        if (dis[i-1] >= dis[i])
            dis[i-1] = dis[i], ans--;
    }
    cout << ans << endl;
    return 0;
}

Simple And Clear