首页 > 试题广场 >

堆棋子

[编程题]堆棋子
  • 热度指数：260 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小易将n个棋子摆放在一张无限大的棋盘上。第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子。每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数.

输入描述:
输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数
第二行为n个棋子的横坐标x[i](1 ≤ x[i] ≤ 10^9)
第三行为n个棋子的纵坐标y[i](1 ≤ y[i] ≤ 10^9)


输出描述:
输出n个整数,第i个表示棋盘上有一个格子至少有i个棋子所需要的操作数,以空格分割。行末无空格

如样例所示:
对于1个棋子: 不需要操作
对于2个棋子: 将前两个棋子放在(1, 1)中
对于3个棋子: 将前三个棋子放在(2, 1)中
对于4个棋子: 将所有棋子都放在(3, 1)中
示例1

输入

4
1 2 4 9
1 1 1 1

输出

0 1 3 10
算法知识视频讲解
添加回答
pein531头像 pein531

穷举

枚举最终棋子所在的位置，让所有的棋子往这个位置移动（最近的先移动过来），计算最小的移动代价。 
import java.lang.String;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null){
            int n = Integer.parseInt(line);
            String[] params = br.readLine().split(" ");
            int[] x = new int[n];
            for(int i = 0; i < n; i++){
                x[i] = Integer.parseInt(params[i]);
            }
            params = br.readLine().split(" ");
            int[] y = new int[n];
            for(int i = 0; i < n; i++){
                y[i] = Integer.parseInt(params[i]);
            }
            System.out.println(solve(n, x, y));
        }
    }
    
    private static String solve(int n, int[] x, int[] y) {
        int[] res = new int[n];
        Arrays.fill(res, Integer.MAX_VALUE);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        // 枚举所有可能的位置
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                // 让所有的棋子移动到(i,j)位置
                for(int k = 0; k < n; k++){
                    pq.offer(Math.abs(x[i] - x[k]) + Math.abs(y[j] - y[k]));
                }
                int dis = 0, index = 0;
                while(!pq.isEmpty()){
                    dis += pq.poll();
                    res[index] = Math.min(res[index], dis);
                    index++;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            sb.append(res[i] + " ");
        }
        return sb.toString().trim();
    }
}

发表于 2022-02-25 16:32:01 回复(0)
Buendia94头像 Buendia94
n, i = list(map(int, input().split(' ')))
sum = 0
if n % 2 == 1:
    num_left = int((n-1)/2)
    if i > num_left:
        for j in range(num_left):
            sum = sum + 2 * (j + 1) 
        for j in range(i - num_left - 1):
            sum = sum + 2 * (j + 1)
    elif i <= num_left:
        for j in range(i - 1):
            sum = sum + 2 * (j + 1)
    
else:
    num_left = int(n/2)
    if i > num_left:
        for j in range(num_left):
            sum = sum + 2 * (j + 1)
        for j in range(i - num_left -1):
            sum = sum + 2 * (j + 1)
    elif i <= num_left:
        for j in range(i - 1):
            sum = sum + 2 * (j + 1)

print(sum)
发表于 2020-06-09 02:04:49 回复(0)
往事随风丶头像 往事随风丶
import numpy as np
n=int(input())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
def c_list(n,x,y):
c=[]
x=np.array(x)
y=np.array(y)
for i in range(n):
#print(x[:i+1])
midx,midy=np.sum(x[:i+1])//(i+1),np.sum(y[:i+1])//(i+1)
#print(midx,midx)
c_i=np.sum(np.fabs(x[:i+1]-midx)+np.fabs(y[:i+1]-midy))
#print(np.fabs(x[:i+1]-midx))
#print(np.fabs(y[:i+1]-midy))
c.append(c_i)
return c
for i in c_list(n,x,y):
print(int(i),end=' ')


发表于 2019-08-03 00:23:53 回复(0)
提交观点

问题信息

模拟 网易 算法工程师 2018
上传者：小小
难度：
3条回答 1564浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号