ZYF037 两地调度
大约 3 分钟贪心
ZYF037 两地调度
【算法标签】 贪心
【语法标签】 :结构体(struct)、sort、自定义比较函数(cmp)、long long、cin/cout、for循环、数组
公司要面试 个人。每个人需要飞到 A 市或 B 市,飞往 A 市的费用是 ,飞往 B 市的费用是 。要求最终 A 市和 B 市各有 人。在满足这个条件下,求最小总费用。
数据范围:,费用均为非负整数。
二、解题思路
数据规模分析
最大到 ,意味着 的排序算法是可行的,暴力枚举组合()绝对不可行。
贪心策略推导
直接分配很困难——每个人有去 A 和去 B 两种选择,我们需要从 人中选 人去 A,剩下 人去 B。看起来像是一个组合问题。
换一个角度思考:假设先让所有人都去 A,总费用就是 。但是 B 市还缺 个人,所以需要从这 人中挑 个人"改签"到 B。
对于第 个人,从 A 改签到 B 的费用变化是:
- 如果 ,说明这个人去 B 比去 A 便宜,改签反而省钱;
- 如果 ,说明这个人去 B 更贵,改签会多花钱。
我们的总费用 = 所有人都去 A 的费用 + 选中改签去 B 的 个人的 之和。
要使总费用最小,就应该选 最小的 个人改签去 B。
算法流程
- 读入所有人的 和 。
- 计算每个人的差值 。
- 按 从小到大排序。
- 前 个( 最小的)去 B,后 个去 A。
- 累加费用,输出答案。
手动模拟样例
样例输入:(共 4 人,A、B 各 2 人)
| 第 i 人 | |||
|---|---|---|---|
| 1 | 10 | 20 | +10 |
| 2 | 30 | 200 | +170 |
| 3 | 400 | 50 | -350 |
| 4 | 30 | 20 | -10 |
按 从小到大排序:
| 排名 | 原编号 | 最终去 | |
|---|---|---|---|
| 1 | 3 | -350 | B (50) |
| 2 | 4 | -10 | B (20) |
| 3 | 1 | +10 | A (10) |
| 4 | 2 | +170 | A (30) |
总费用 = ,与样例一致。
另一种理解方式
本质上是:对每个人计算"选 B 比选 A 便宜多少(如果为负说明 B 更贵)",便宜得最多的 个人去 B,其余去 A。贪心是正确的,因为这个"便宜程度"互相独立,不会因为别人的选择而改变。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5; // 总共2n个人
struct Person {
int a, b, d; // a: 去A费用, b: 去B费用, d: b-a差值
};
Person p[N];
// 按差值从小到大排序
bool cmp(Person x, Person y) {
return x.d < y.d;
}
int main() {
int n; // 注意:输入的n就是costs的长度,即2n个人中的总人数的一半
cin >> n; // 实际上这里是总人数的一半,共2n个人
// 但题目输入的第一行n是数组长度含义...
// 此处按样例逻辑:第一行输入的是总人数的一半,即A、B各需要的人数
// 重新读题:输入第一行n表示costs的长度=2n
// 我们设m = n 为一半人数,总人数 = 2*m
int m = n; // m = A和B各需要的人数
int total = 2 * m; // 总人数
for (int i = 1; i <= total; i++) {
cin >> p[i].a >> p[i].b;
p[i].d = p[i].b - p[i].a; // 计算差值
}
// 按差值升序排序
sort(p + 1, p + total + 1, cmp);
// 前m个(差值最小)去B,后m个去A
long long ans = 0;
for (int i = 1; i <= m; i++) {
ans += p[i].b; // 差值最小的m个人去B
}
for (int i = m + 1; i <= total; i++) {
ans += p[i].a; // 差值最大的m个人去A
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:排序 ,累加 ,总复杂度 ,在 范围内完全可行。
- 空间复杂度:结构体数组存储 。
