外卖递送 码蹄集
外卖
2023-09-11 14:16:29 时间
题目来源:码蹄集
题目描述:
算法思路:
1. 对居民的位置进行排序;
2. 取中位数作为外卖站的位置,因为到每个居民的距离之和最小,必然在某个居民的位置或者两个居民的位置之间;
3. 计算每个居民到外卖站的距离之和。
B站老师思路讲解链接:https://www.bilibili.com/video/BV1MX4y1R77W/?t=519.4&vd_source=3ae2a916df1bc5c1114c2bf3e95a2118
C++代码实现:
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
// 如果 n 为奇数,则站点建在最中间的居民处最优
if (n % 2 == 1) {
int center = a[n / 2];
long long dist = 0;
// 统计到每个居民的距离之和
for (int i = 0; i < n; i++) {
dist += abs(a[i] - center);
}
cout << dist << endl;
}
// 如果 n 为偶数,则站点建在最中间的两个居民中任意一个处最优
else {
int left_center = a[n / 2 - 1];
int right_center = a[n / 2];
long long dist_left = 0, dist_right = 0;
// 计算左右两个站点的距离之和,并取其较小值
for (int i = 0; i < n; i++) {
dist_left += abs(a[i] - left_center);
dist_right += abs(a[i] - right_center);
}
cout << min(dist_left, dist_right) << endl;
}
return 0;
}
Java代码实现:
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
Arrays.sort(a);
// 如果 n 为奇数,则站点建在最中间的居民处最优
if (n % 2 == 1) {
int center = a[n / 2];
long dist = 0;
// 统计到每个居民的距离之和
for (int i = 0; i < n; i++) {
dist += Math.abs(a[i] - center);
}
System.out.println(dist);
}
// 如果 n 为偶数,则站点建在最中间的两个居民中任意一个处最优
else {
int left_center = a[n / 2 - 1];
int right_center = a[n / 2];
long dist_left = 0, dist_right = 0;
// 计算左右两个站点的距离之和,并取其较小值
for (int i = 0; i < n; i++) {
dist_left += Math.abs(a[i] - left_center);
dist_right += Math.abs(a[i] - right_center);
}
System.out.println(Math.min(dist_left, dist_right));
}
}
}
Python代码实现(会错一个测试用例):
n = int(input())
a = list(map(int, input().split()))
a.sort()
mid = (a[n // 2] + a[(n - 1) // 2]) // 2 # 取中位数
ans = sum(abs(x - mid) for x in a)
print(ans)
代码提交测试结果:
相关文章
- Java实现第十届蓝桥杯外卖店优先级
- Java实现第十届蓝桥杯外卖店优先级
- Java实现第十届蓝桥杯外卖店优先级
- Java实现第十届蓝桥杯外卖店优先级
- Java实现第十届蓝桥杯外卖店优先级
- 百度外卖面试
- 跨平台 动态化 董尚先 美团外卖 Flutter 动态化实践
- 设计模式在外卖营销业务中的实践
- 35岁遇“中年危机”!失业后,除了送外卖和跑滴滴,还能做什么?
- 蓝桥杯2019省赛——外卖店优先级(Java)
- 外卖必不可少,咋确定好不好吃呢~ python采集数据信息
- 「美团外卖APP签约快捷支付」流程体验
- 30岁本科男,在测试行业干了五年还只会功能测试,难道真的要去送外卖吗?
- 跳出舒适圈的程序员3年月薪还没到2万,干脆考虑转行送外卖!
- 看到35岁程序员转行开网约车/送外卖,是程序员们自嘲的段子还是现状?
- 月薪3万的大厂程序员裸辞3个月,送外卖谋生背后的真实感悟
- 自动化测试在美团外卖的实践与落地
- 【快来投票】除了外卖滴滴,35岁之后你还能做什么行业
- 大学毕业熬过了失业失恋,送了2个月外卖,熬不住哭了一整晚
- 刷题记录:牛客NC13224送外卖
- CompletableFuture进阶篇-外卖商家端API的异步化
- 美团外卖——物流论文小笔记(Python实现)
- 基于SpringCloud+redis+Springsecurity实现的微信小程序外卖系统