题解 | #合并果子#

合并果子

https://www.nowcoder.com/practice/854e7118eb08464ab8ce7a0bca8b276c

解题思路

这是一道关于二维平面上点的合并问题。主要思路如下：

问题分析：
- $N$ 个果子在二维平面上，每个果子有位置 $(X_i, Y_i)$ 和重量 $W_i$
- 每次合并消耗的体力为 $W_i$ 乘 Manhattan距离
- 需要找到一个最优的合并中心点，使得总体力消耗最小
解题思路：
- 利用重量中位数性质找到最优合并点
- 分别在 $x$ 轴和 $y$ 轴上找到重量中位数对应的坐标
- 选取距离该点最近的几个点作为候选合并中心
- 计算所有点到每个候选中心的总体力消耗，取最小值
关键点：
- 按 $x$ 坐标和 $y$ 坐标分别排序
- 找到重量中位数对应的位置
- 选取靠近重量中心的前10个点作为候选点

代码

cpp
java
python

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

struct node {
    int x, y, w;
};

// 找到重量中位数对应的点
node find(vector<node>& pos, LL total) {
    LL target = total >> 1;
    LL tmp = 0;
    for(auto it : pos) {
        tmp += it.w;
        if(tmp > target) return it;
    }
    return pos.back();
}

int main() {
    int n;
    cin >> n;
    vector<node> pos(n);
    LL total = 0;
    for(int i = 0; i < n; ++i) {
        cin >> pos[i].x >> pos[i].y >> pos[i].w;
        total += pos[i].w;
    }
    
    // 找x坐标的重量中位数
    sort(pos.begin(), pos.end(), [](node& a, node& b) { return a.x < b.x; });
    int x = find(pos, total).x;
    
    // 找y坐标的重量中位数
    sort(pos.begin(), pos.end(), [](node& a, node& b) { return a.y < b.y; });
    int y = find(pos, total).y;
    
    // 按到重量中心的距离排序
    sort(pos.begin(), pos.end(), [=](node& a, node& b) {
        return abs(a.x - x) + abs(a.y - y) < abs(b.x - x) + abs(b.y - y);
    });
    
    // 计算最小体力消耗
    LL res = LLONG_MAX;
    for(int j = 0; j < min(10, n); ++j) {
        LL tmp = 0;
        for(auto it : pos) {
            tmp += (LL)it.w * (abs(it.x - pos[j].x) + abs(it.y - pos[j].y));
        }
        res = min(res, tmp);
    }
    cout << res << endl;
    return 0;
}

import java.util.*;

public class Main {
    static class Node {
        int x, y, w;
        Node(int x, int y, int w) {
            this.x = x;
            this.y = y;
            this.w = w;
        }
    }
    
    static Node find(List<Node> pos, long total) {
        long target = total >> 1;
        long tmp = 0;
        for(Node node : pos) {
            tmp += node.w;
            if(tmp > target) return node;
        }
        return pos.get(pos.size() - 1);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Node> pos = new ArrayList<>();
        long total = 0;
        
        for(int i = 0; i < n; i++) {
            Node node = new Node(sc.nextInt(), sc.nextInt(), sc.nextInt());
            pos.add(node);
            total += node.w;
        }
        
        // 找x坐标的重量中位数
        pos.sort((a, b) -> a.x - b.x);
        int x = find(pos, total).x;
        
        // 找y坐标的重量中位数
        pos.sort((a, b) -> a.y - b.y);
        int y = find(pos, total).y;
        
        // 按到重量中心的距离排序
        final int finalX = x, finalY = y;
        pos.sort((a, b) -> {
            int distA = Math.abs(a.x - finalX) + Math.abs(a.y - finalY);
            int distB = Math.abs(b.x - finalX) + Math.abs(b.y - finalY);
            return distA - distB;
        });
        
        // 计算最小体力消耗
        long res = Long.MAX_VALUE;
        for(int j = 0; j < Math.min(10, n); j++) {
            long tmp = 0;
            Node center = pos.get(j);
            for(Node node : pos) {
                tmp += (long)node.w * (Math.abs(node.x - center.x) + Math.abs(node.y - center.y));
            }
            res = Math.min(res, tmp);
        }
        System.out.println(res);
    }
}

class Node:
    def __init__(self, x, y, w):
        self.x = x
        self.y = y
        self.w = w

def find(pos, total):
    target = total >> 1
    tmp = 0
    for node in pos:
        tmp += node.w
        if tmp > target:
            return node
    return pos[-1]

n = int(input())
pos = []
total = 0

# 读入数据
for _ in range(n):
    x, y, w = map(int, input().split())
    pos.append(Node(x, y, w))
    total += w

# 找x坐标的重量中位数
pos.sort(key=lambda node: node.x)
x = find(pos, total).x

# 找y坐标的重量中位数
pos.sort(key=lambda node: node.y)
y = find(pos, total).y

# 按到重量中心的距离排序
pos.sort(key=lambda node: abs(node.x - x) + abs(node.y - y))

# 计算最小体力消耗
res = float('inf')
for j in range(min(10, n)):
    tmp = 0
    for node in pos:
        tmp += node.w * (abs(node.x - pos[j].x) + abs(node.y - pos[j].y))
    res = min(res, tmp)

print(res)