自动搬运

查看原文

来自洛谷，原作者为

	Ciyang 白昼之光 , 岂知夜色之深。

搬运于2025-08-24 21:40:32，当前版本为作者最后更新于2018-08-10 09:12:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本弱已AC,这是一道模拟题,可以按照题意做,但这道题也有几个技巧问题

思路比较简单:
定义结构体,其中定义了是否到达底部的函数,和向下走(y-1)的函数,输入数据后对这n个结构体,由y的大小从小到大排序
模拟环节可以设置一个循环每一秒进行,在循环外定义一个布尔值变量successful是用来记录是否成功的,定义一个变量来记录当前要接的金币的代号,我设置默认为假
循环中(重点):要先监测所有金币当前是否已经由掉到y=0的情况,然后自己的x坐标与此金币的x坐标比较是否相等,不相等则跳出循环,相等就继续监测直到最后一个,这里可以提前跳出循环(剪枝?)也可以不用,不会超时
接着就是此秒内自己和金币的移动,自己的移动就像游戏一样,如果当前要接的金币在左自己就左移,金币在右自己就右移.金币移动也有个小技巧:如果不是0则下落,当然如果你与我一样把监测金币放循环最前面应该不需要这样了.
还有一个可能会出现的疑问是为什么不把金币下落和监测金币函数放在一起,解释一下:因为两个函数一个在循环开始,一个在循环结束所以分开写,放在一块就是都放在最前面好像也可以.
提一下我的代码中数组编号是从0开始的

表达可能不太清楚,如果不理解可以看代码

代码:

#include<iostream>
#include<stdio.h>
#include<algorithm> 
using namespace std;
struct coin{
	//金币的结构体
	int nx;
	int ny;
	void down(){
    //金币下落实现,如果y不为0则下落
		if(ny!=0)ny-=1;
	}
	bool havedown(){
    //监测金币是否坐标已经为0
		if(ny==0)return true;
		else return false;
	}
};
bool coinscmp(coin a,coin b){
	//金币的y坐标比较,重载排序函数
	return a.ny<b.ny;
}
int main(){
	int t;cin>>t;
	for(int groupn=0;groupn<t;groupn++){
		int n;cin>>n;
		coin coins[n];
		for(int i=0;i<n;i++){
        //从0到n-1进行赋值
			cin>>coins[i].nx>>coins[i].ny;
		}
		sort(coins,coins+n,coinscmp);
        //对金币进行sort排序
		int mx=0,my=0,i=0;
        //i记录当前要接住哪个金币
		bool successful=false;
        //记录是否成功
		while(1){
			if(i==n){
            //如果现在要接的金币已经是第n个(不存在的那个)则成功
				successful=true;
				break;
			}
			bool thissuccessful=true;
            //记录本秒所有要接住的金币是否成功接住
			for(int j=i;j<n;j++){
            //从i开始到最后一个
				if(coins[j].havedown()==true){
                //是不是第j个金币的y已经为0
					if(mx==coins[j].nx){
						i+=1;
					}
					else{
                    //如果接住不
						thissuccessful=false;
						break;
					} 
				}
                //这里可以优化,遇到false跳出
			}
			if(thissuccessful==false)break;
			if(mx<coins[i].nx)mx+=1;
			if(mx>coins[i].nx)mx-=1;
			for(int j=i;j<n;j++)coins[j].down();
            //自己和金币的移动
		}
		if(successful==true)printf("Abletocatch\n");
		else printf("Notabletocatch\n");
        //输出结果
	}
    return 0;
}