【codeforces 350C】Bombs

【题解】

会发现在x轴以及y轴上的炸弹,能用较少的操作数除掉。
而其他的点,会发现操作数都是一样的。
那么先把x,y轴上的点都除掉。
其他点。
我们优先沿着横坐标轴移动到和它相同位置。
然后再改变y坐标和目标炸弹一致。
然后就会发现。
x相同的话,要以y坐标的绝对值升序排,要优先处理y的绝对值小的点。
不然可能会出现走的过程中遇到另外一个炸弹的情况。
sort一波+贪心就好。

【代码】

#include <bits/stdc++.h>

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

using namespace std;

const int N = 1e5;

struct abc{

    int x,y;

};

int n,cnt;

abc a[N+10];

bool cmp1(abc a,abc b){

    return a.y<b.y;

}

bool cmp2(abc a,abc b){

    return a.x<b.x;

}

bool cmp3(abc a,abc b){

    if (a.x!=b.x)

        return a.x<b.x;

    else {

        if (a.y<0 && b.y<0){

            return a.y>b.y;

        }else return a.y<b.y;

    }

}

int main()

{

    scanf("%d",&n);

    rep1(i,1,n){

        scanf("%d%d",&a[i].x,&a[i].y);

        if (a[i].x==0 || a[i].y==0) cnt++;

    }

    printf("%d\n",cnt*4+(n-cnt)*6);

    //从下到上排序.

    sort(a+1,a+1+n,cmp1);

    rep1(i,1,n)

        if (a[i].x==0){

            if (a[i].y>0){

                printf("1 %d U\n",a[i].y);

                puts("2");

                printf("1 %d D\n",a[i].y);

                puts("3");

            }

        }

    rep2(i,n,1)

        if (a[i].x==0){

            if (a[i].y<0){

                printf("1 %d D\n",-a[i].y);

                puts("2");

                printf("1 %d U\n",-a[i].y);

                puts("3");

            }

        }

    //从左往右排序

    sort(a+1,a+1+n,cmp2);

    rep1(i,1,n)

        if (a[i].y==0){

            if (a[i].x>0){

                printf("1 %d R\n",a[i].x);

                puts("2");

                printf("1 %d L\n",a[i].x);

                puts("3");

            }

        }

    rep2(i,n,1)

        if (a[i].y==0){

            if (a[i].x<0){

                printf("1 %d L\n",-a[i].x);

                puts("2");

                printf("1 %d R\n",-a[i].x);

                puts("3");

            }

        }

    sort(a+1,a+1+n,cmp3);

    rep1(i,1,n)

        if (a[i].x!=0 && a[i].y!=0){

            printf("1 %d ",abs(a[i].x));if (a[i].x<0) puts("L");else puts("R");

            printf("1 %d ",abs(a[i].y));if (a[i].y<0) puts("D");else puts("U");

            puts("2");

            printf("1 %d ",abs(a[i].y));if (a[i].y<0) puts("U");else puts("D");

            printf("1 %d ",abs(a[i].x));if (a[i].x<0) puts("R");else puts("L");

            puts("3");

        }

    return 0;

}

巴特西

【codeforces 350C】Bombs

最新文章

热门文章