洛谷P2694 接金币

url : https://www.luogu.com.cn/problem/P2694

tag：
模拟

思路：
为了可以接到所有的金币，所以我们可以采取一个贪心的策略，每次都先去接高度距离自己最近的一个金币，之后判断在这个过程中是否存在接不到的情况，如果有就说明接不到所有的金币，否则就是可以接到所有的金币。
为了采取贪心的策略，我们需要对所有的金币按照高度排序。然后需要维护一个全局的掉落高度 ey 和自己的位置 fx ，之后按照高度遍历每一个金币，判断，当我走到这个金币的时候金币到我的高度，如果大于等于0则说明可以接到，否则接不到。如果可以接到，则更新一下ey和fx。
关于如何排序，可以利用pair的特性，即先按照first排序如果一样再按照second排序，来排。所以我们可以用pair来存每一个金币的位置，且将高度放到first。
关于如何判断，因为题目有给一个速度都是1，所以移动的距离（用绝对值表示）就是这一段时间，即从原来我的位置到要接的那个金币下面的时间，金币下降的高度。所以先让 ey += abs(fx - dp[i].second),之后再判断 dp[i].first - ey 的大小。如果大于0就可以接到，小于零就break掉。
当大于0时，为了可以接到，所以必须让金币的高度为0，因此就还要等一段时间，这段时间fx不会更新，但是ey需要再加上 dp[i].first - ey, 表示在等待的过程中全局的下降距离增加的距离。
ps：如果速度不为1可能反而会好理解一点。

代码：

#include <iostream>  
#include <algorithm>  
using namespace std;  
typedef pair<int, int> PII;  
PII dp[52];  
int main()  
{  
    int g;  
    cin >> g;  
    while(g--)  
    {  
        int n;  
        bool flag = true;  
        cin >> n;  
        int fx = 0, ey = 0;  
        for (int i = 0; i < n; i ++)  
        {  
            cin >> dp[i].second >> dp[i].first;  
        }  
        sort(dp, dp + n);  
        for (int i = 0; i < n; i ++)  
        {  
            ey += abs(fx - dp[i].second);  
            if (dp[i].first - ey >= 0)  
            {  
                ey += dp[i].first - ey;  
                fx = dp[i].second;  
            }  
            else  
            {  
                flag = false;  
                cout << "Notabletocatch\n";  
                break;  
            }  
        }  
        if (flag) cout << "Abletocatch\n";  
    }  
    return 0;  
}