zzuli 1530 小L玩滚球游戏——————思维

比眉伴天荒 2021-11-26 20:44 174阅读 0赞

## [1530: 小L玩滚球游戏][1530_ _L] ##

时间限制: 1 Sec 内存限制: 128 MB  
提交: 54 解决: 18

**题目描述**  
小L正在玩滚球游戏，有n个水晶球在轨道上以不同开始位置和速度从近往远的方向滚动，如果两个水晶球在滚动过程中相遇，它们就会融合成一个水晶球，然后以速度较慢的水晶球的速度继续向前滚动， 问经过时间t后，轨道上还有多少水晶球。  
输入  
第一行输入两个整数n、t，n代表水晶球的数量（1 <= n <= 105, 0<t<231），t代表时间。  
接下来n行，每行两个整数，按位置从近到远的顺序给出水晶球的初始位置和速度。  
输出  
输出一个整数表示经过时间t后水晶球的数量。  
**样例输入**  
5 3  
0 1  
1 2  
2 3  
3 2  
6 1  
**样例输出**  
3

--------------------

//#include<bits/stdc++.h>
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<map>
    #include<bitset>
    #include<set>
    #include<vector>
    
    
    using namespace std;
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e5+7;
    
    ll p[MAXN];
    
    int main(){
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            ll n,t;
            while(~scanf("%lld %lld",&n,&t)){
        
                    for(int i=0;i<n;++i){
        
                            ll x,y;
                            scanf("%lld %lld",&x,&y);
                            p[i] = x + y * t;
                    }
                    ll num = n;
                    for(int i=n-1;i>0;--i){
        
                            if(p[i-1]>=p[i]){
        
                                    p[i-1] = p[i];
                                    num--;
                            }
                    }
                    printf("%lld\n",num);
            }
    
            return 0;
    }

[1530_ _L]: http://acm.zzuli.edu.cn/problem.php?id=1530