CF350C 题解

ikunTLE · 2024-12-06 19:01:32 · 题解

题目传送门

思路

先说如何求 k 的值。机器人必须捡起一个炸弹后必须要返回 (0,0) 点销毁炸弹，再去下一个点找炸弹。设第 i 个点的坐标为 (X_i,Y_i)，若 X_i\ne0，k\gets k+2，这是一去一回的总和，否则 k 不变；同理，若 Y_i\ne0，k\gets k+2。最后，还需要再操作一次 k\gets k+2，这是捡起和销毁炸弹的操作。

再说如何模拟机器人运动路线。由于机器人在路上不能碰到炸弹，我们可以用坐标 (X_i,Y_i) 距离 (0,0) 点的距离排序，即 \lvert X_i\rvert+\lvert Y_i\rvert。这样可以保证机器人路上不会碰到炸弹，因为假设机器人在一次查找的路上碰到了炸弹，那么这个炸弹距离 (0,0) 点的距离一定更短，已经被销毁了。这样，我们可以依次移动两个坐标，到达目标点捡起炸弹，在以相反的方向回到 (0,0) 点销毁炸弹。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e5+10;
struct node{
    int x,y;
    friend bool operator<(const node cmp_x,const node cmp_y){
        int dis1=(int)abs(cmp_x.x)+(int)abs(cmp_x.y);
        int dis2=(int)abs(cmp_y.x)+(int)abs(cmp_y.y);
        return dis1<dis2;
    }
}a[N];
int main(){
    int n=read();
    for(int i=1;i<=n;++i)
        a[i]={read(),read()};
    sort(a+1,a+n+1);
    int sum=0;
    for(int i=1;i<=n;++i)
        sum+=(bool)a[i].x*2+(bool)a[i].y*2+2;
    printf("%d\n",sum);
    for(int i=1;i<=n;++i){
        if(a[i].x<0)
            printf("1 %d L\n",-a[i].x);
        else if(a[i].x>0)
            printf("1 %d R\n",a[i].x);
        if(a[i].y<0)
            printf("1 %d D\n",-a[i].y);
        else if(a[i].y>0)
            printf("1 %d U\n",a[i].y);
        printf("2\n");
        if(a[i].x<0)
            printf("1 %d R\n",-a[i].x);
        else if(a[i].x>0)
            printf("1 %d L\n",a[i].x);
        if(a[i].y<0)
            printf("1 %d U\n",-a[i].y);
        else if(a[i].y>0)
            printf("1 %d D\n",a[i].y);
        printf("3\n");
    }
    return 0;
}