USACO备考冲刺必刷题 | P2694 接金币

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：

【题目描述】

在二维坐标系里，有 n 个金币，编号 0～n?1。初始时，第 i 个金币位于 (xi,yi)。所有的金币每秒向下垂直下降 1 个单位高度。例如有个金币当前坐标是 (x,y)，那么 t 秒后金币所在的位置就是(x,y?t)。初始时，FJ 在 (0,0) 处，FJ 每秒只能向左右移动 1 个单位距离，当然 FJ 也可以不移动。如果在某个时刻某个金币和 FJ 所在的位置重合，那么 FJ 就能接住这个金币。求 FJ 能否把所有的金币都接住，如果行输出 Abletocatch，否则输出 Notabletocatch。

【输入】

本题有 g 组数据。

第一行，一个整数 g，表示有 g 组测试数据。

对于每组测试数据，格式如下：

第一行，一个整数 n。

接下来有 n 行，第 i 行两个整数表示 xi,yi。

【输出】

共 g 行，每行输出 AbletocatchAbletocatch 或 NotabletocatchNotabletocatch。

【输入样例】

【输出样例】

AbletocatchNotabletocatchNotabletocatchAbletocatchNotabletocatch

【代码详解】

#include using namespace std;int g, n;struct node { int x, y;}p[55];bool cmp(node a, node b){ return a.y < b.y;}int main{ cin >> g; // 输入g while (g--) { // 遍历g次询问 cin >> n; // 输入n memset(p, 0, sizeof(p)); // 每次将p数组重新初始化 p[0].x = 0, p[0].y = 0; // 定义第一个金币 for (int i=1; i<=n; i++) { // 遍历n个金币 cin >> p[i].x >> p[i].y; // 输入x和y坐标 } sort(p+1, p+n+1, cmp); // 按照y坐标从小到大排序 int cnt=0; // 定义计数器 for (int i=1; i<=n; i++) { // 遍历n个金币 if (abs(p[i].x-p[i-1].x)<=abs(p[i].y-p[i-1].y)) { // 当前金币和前一个金币的x坐标差的绝对值小于等于y坐标差的绝对值 cnt++; // 计数器自增1 } } if (cnt==n) cout << "Abletocatch" << endl; // 如果n个金币都满足，说明所有金币都可以接到 else cout << "Notabletocatch" << endl; // 否则打印Notabletocatch } return 0;}

【运行结果】

53-1 11 30 4Abletocatch1-3 2Notabletocatch3-1 11 20 4Notabletocatch30 9-1 11 3Abletocatch870 141-108 29952 402-70 28084 28-29 36366 427-33 232Notabletocatch