题解 P6317 【[COCI2006-2007#3] TENKICI】

· · 题解

题目描述

在 n \times n 的网格中，使每一排，每一列都只有一个棋子，求方案步数的最小值。

分析

我们发现每一排，每一列是不影响的，那么可以考虑先按 x 轴排序，再按 y 轴排序，贪心的选取第 i 个。证明：

\text{有以下原坐标排序:} \ a_1\le a_2 \le a_3 \le ...\le a_n ans_1= \sum_i^n abs(a_i-i) \text{若交换第x,y个(x < y):} ans_2 = \sum_{i,i \neq x,y}^nabs(a_i-i)+abs(a_x-y)+abs(a_y-x) abs(a_x-x)+ abs(a_y-y) \le abs(a_x-y)+ abs(a_y-x)

因为点 (a_x,a_y) 一定在直线 y=x 之上，所以 (x,y) 的曼哈顿距离一定比 (y,x) 更短

所以由小到大一定最优。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5110;
struct node
{
    int x,y,id; 
}s[N];
struct Q{
    int id,M;
    char A;
}st[N];
inline int read()
{
    int t=0,f = 0;char a=getchar();
    while(a<'0'||a>'9'){if(a=='-')f=1;a=getchar();}
    while(a>='0'&&a<='9'){t=(t<<1)+(t<<3)+a-'0';a=getchar();}
    return f?-t:t;
}
bool cmp1(node a,node b)
{
    return a.x<b.x;
}
bool cmp2(node a,node b)
{
    return a.y<b.y;
}
long long n,ans = 0,top = 0;
int main()
{
    n = read();
    for(int i = 1;i <= n;i++)
    s[i].x = read(),s[i].y = read(),s[i].id = i;
    sort(s+1,s+1+n,cmp1);
    for(int i = 1;i <= n;i++)
    {
        int f = s[i].x - i;
        ans += abs(f);
        if(f < 0)
        {
            st[++top].id = s[i].id;
            st[top].M = abs(f);
            st[top].A = 'D';
        }
        if(f > 0)
        {
            st[++top].id = s[i].id;
            st[top].M = abs(f);
            st[top].A = 'U';
        }
    }
    sort(s+1,s+1+n,cmp2);
    for(int i = 1;i <= n;i++)
    {
        int f = s[i].y - i;
        ans += abs(f);
        if(f < 0)
        {
            st[++top].id = s[i].id;
            st[top].M = abs(f);
            st[top].A = 'R';
        }
        if(f > 0)
        {
            st[++top].id = s[i].id;
            st[top].M = abs(f);
            st[top].A = 'L';
        }
    }
    printf("%lld\n",ans);
    for(int i = 1;i <= top;i++)
    {
        for(int j = 1;j <= st[i].M;j++)
        {
            printf("%d %c\n",st[i].id,st[i].A);
        }
    }
}

博客地址