首页 > 试题广场 >

棋盘

[编程题]棋盘

热度指数：299 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

假设此时我们有一个足够大的棋盘，棋盘上每个格子的位置我们都用坐标(X, Y)来表示。棋盘上已经摆放了若干个可以移动的棋子，棋子每一次移动都可以向上，向下，向左或向右移动一个单位长度。
我们此刻想通过若干次移动，将所有棋子最后摆成一个彼此靠近的水平线，这样他们最后的坐标就是(X, Y), (X+1, Y), ....., (X+N, Y)。水平线上的棋子最后的顺序以及整数X和Y都是任意的。
我们的问题是求完成这样的目标，最少需要移动几步。
注意：任何时候同一个格子内都不可以同时放两个或两个以上的棋子(棋子不可堆叠)。

输入描述:

输入文件一共有n+1行。

第1行为一个正整数n，1<=n<10000, n为棋子的数量。

从第2行开始一直到n+1行，一共n行，分别描述的是n个棋子各自的初始位置。每一行均为用空格分开的两个整数x[i], y[i]， 他们表示第i个棋子的坐标，-10000<=x[i],y[i]<=10000。

输出描述:

输出仅有1行，它的值为将棋子移动到目标位置所需的最少步数。

示例1

输入

输出

算法知识视频讲解

C/C++

deng丶

个人思路：按x坐标对坐标有小到大进行排序，先只移动x，例如设（X2，Y2）为基准坐标，则将各个坐标分别移动到(X2 - 1, Y1), (X2, Y2), ....., (X2+N - 1, Yn)，得到出步数最少的移动方案，同理再移动y

，设某一坐标所在行为目标行，将其他所有坐标移动到该行，移动步数等于坐标所在行的行数-目标行的行数的绝对值，例如设Y1为目标行，则移动步数sum_y = abs(Y2 - Y1) +...+abs（Yn - Y1),最后将最小的sum_x、sum_y相加就得到最小的移动步数。

#include <iostream>

#include <vector>
#include <algorithm>

using namespace std;

int coo_sort(pair<int, int> a, pair<int, int> b)
{
return a.first < b.first;

}

int mov_x(int i, vector<pair<int, int>> coo)
{
    int sum = 0;
    for (int j = i; j > 0; j--)
     {
        if (coo[j].first == coo[j - 1].first)
        {
            coo[j - 1].first = coo[j].first - 1;
            sum++;
        }
        else
        {
            sum += coo[j].first - coo[j - 1].first - 1;
            coo[j - 1].first = coo[j].first - 1;
        }
    }
    for (int j = i; j < coo.size() - 1; j++)
    {
        if (coo[j].first == coo[j + 1].first)
        {
            coo[j + 1].first = coo[j].first + 1;
            sum++;
        }
        else
        {
            sum += coo[j + 1].first - coo[j].first - 1;
            coo[j + 1].first = coo[j].first + 1;
        }
    }
    return sum;
}

int mov_y(int i, vector<pair<int, int>> coo)
{
    int sum = 0;
    for (int j = 0; j < coo.size(); j++)
    {
        sum += abs(coo[i].second - coo[j].second);
    }
    return sum;
}

int main()
{
int n;
vector<pair<int, int>> coo;
pair<int, int> coo_t;
int sum_x,sum_y;
int t;
while (cin >> n)
{
sum_x = 0;
sum_y = 0;
for (int i = 0; i < n; i++)
{
cin >> coo_t.first >> coo_t.second;
coo.push_back(coo_t);
}
sort(coo.begin(), coo.end(), coo_sort);//按x坐标排序

sum_x = mov_x(0, coo);

for (int i = 1; i < coo.size(); i++)//分别设第i个坐标为基准得到最小的x轴移动步数
{
t = mov_x(i, coo);
if (sum_x > t)
sum_x = t;

}

sum_y += mov_y(0, coo);
for (int i = 1; i < coo.size(); i++)//分别设第i个坐标为基准得到最小的y轴移动步数
{
t = mov_y(i, coo);
if (sum_y > t)
sum_y = t;
}
cout << sum_x + sum_y << endl;
coo.clear();
}
return 0;
}

编辑于 2020-03-02 16:16:44 回复(0)

清雪冰橙

# include<iostream>
#include<cstring>
# include<map>
# include<algorithm>
# include<vector>
# include<cmath>
#include <sstream>
using namespace std;

int n,m;
int x[10010], y[10010], z[10010];

int main(void){
    while(cin>>n){
        for(int i=0; i<n; ++i)
            cin>>x[i]>>y[i];
        sort(y, y+n);
        sort(x, x+n);
        int mid=n/2, y_ans = 0, x_ans = 0;
        for(int i=0; i<n; ++i)
            y_ans += abs(y[i]-y[mid]);
        for(int i=0; i<n; ++i)
            z[i] = x[i] - i;
        int a = z[mid];
        for(int i=0; i<n; ++i)
            x_ans += (abs(x[i]-(a+i)));
        cout<<x_ans+y_ans<<endl;
    }
    return 0;
}

编辑于 2020-03-09 09:45:59 回复(1)

Python3

云溪浮

# 求列表的中位数，传入的列表是经过排序的列表

def median(list):

if len(list) % 2 ==1:

median = list[int(len(list)/2)]

else:

median = int((list[int(len(list)/2)] + list[int(len(list)/2) - 1])/2)

return median

# 将x轴的坐标摆成一个彼此靠近的水平线，即x轴的坐标值为一串连续的整数，基准点就是中位数

def x_step(median, lens,list):

# rang 为连续x值的起点

if median in xx and lens%2 == 0:

# 列表长度为偶数且通过int函数后的中位数为列表中的值时，为保证值的准确给rang +1

rang = median - int(lens/2) + 1

else:

rang = median-int(lens/2)

# (rang, rang+lens)为预期的坐标x值，让xx列表中的值与之一一对应，其差值的和即为最短步数

step = 0

for i in range(rang, rang+lens):

step += abs(list[i-rang]-i)

return step

# 将所有的y坐标移动到其中位数的位置，其和为最短步数；

def y_step(median,list):

step = 0

for i in list:

step += abs(i - median)

return step

n = int(input())

xx, yy = [], []

for i in range(n):

x,y = map(int, input().split())

xx.append(x)

yy.append(y)

len_x = len(xx)

len_y = len(yy)

xx.sort()

yy.sort()

median1 = median(xx)

median2 = median(yy)

min_step = x_step(median1, len_x, xx) + y_step(median2, yy)

print(min_step)

发表于 2023-04-14 14:14:34 回复(0)

attraversiamo

#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
int solution(vector<int>&X,vector<int>&Y){
    int res=0;
    int n=X.size();
    if(n==0) return 0;
    vector<int> tmp=Y;
    sort(Y.begin(),Y.end());
    int mid=Y[n/2];
    sort(X.begin(),X.end());
    int mid_X=X[n/2];
    for(int i=n/2-1;i>=0;i--){
        mid_X--;
        if(X[i]!=mid_X)
            res+=max(mid_X-X[i],X[i]-mid_X);
    }
    mid_X=X[n/2];
    for(int i=n/2+1;i<n;i++){
        mid_X++;
        if(X[i]!=mid_X)
            res+=max(mid_X-X[i],X[i]-mid_X);
    }
    for(int i=0;i<n;i++){
         res+=max(Y[i]-mid,mid-Y[i]);
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    int x,y;
    vector<int> X;
    vector<int> Y;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        X.push_back(x);
        Y.push_back(y);
    }
    cout<<solution(X,Y);
}

发表于 2021-08-18 17:05:26 回复(0)

╭(′•o•′)╭☞就是这个人！

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[]x=new int[n];
        int[]y=new int[n];
        for(int i=0;i<n;i++){
            x[i]=in.nextInt();
            y[i]=in.nextInt();
    }
        Arrays.sort(x,0,n);
        Arrays.sort(y,0,n);
        //到中位数的距离距离小
        int mid=n/2;
        int y_res=0;
        int x_res=0;
        //System.out.println();
        for(int i=0;i<n;i++){
            y_res+=Math.abs(y[i]-y[mid]);
            //System.out.println("y_res"+y_res);
        }

        for(int i=0;i<n;i++){
            //计算x坐标时需要计算其基准值
            int pivot=x[mid]+(i-mid);
            x_res+=Math.abs(x[i]-pivot);
        }
        System.out.println(x_res+y_res);

}


}
参考楼主的java版

发表于 2021-05-12 22:12:58 回复(0)