O - Steps 题解

算法 题解

题目大意

一个人在一个n*m的空间的某一点上，向着一个向量的方向前进，每次都走最大可能的步数，问最终能走多少步？

分析

模拟这个人走路，找到每次走路的最大的步数，然后累加即可。

代码

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define oo 999999999
using namespace std;
int main(void)
{
    long long n,m,xc,yc,k;
    unsigned long long ans=0;
    cin>>n>>m>>xc>>yc>>k;
    for(int i=0;i<k;i++)
    {
        long long xd,yd;
        cin>>xd>>yd;
        long long x,y;
        if(!xd)
            x=oo;
        else if(xd>0)
            x=(n-xc)/xd;
        else
            x=(xc-1)/(-xd);
        if(!yd)
            y=oo;
        else if(yd>0)
            y=(m-yc)/yd;
        else
            y=(yc-1)/(-yd);
        long long t=x>y?y:x;
        xc+=xd*t;
        yc+=yd*t;
        ans+=t;
    }
    cout<<ans<<endl;
    return 0;
}