Leetcode:1029. 两地调度(贪心）

本文链接：https://blog.csdn.net/stackempty2/article/details/109080704

一道关于贪心算法的LeetCode题目，要求将2N个人分配到A、B两个城市，使总费用最低。示例显示，最低费用为110，通过贪心策略，每次选择使得公司花费增加最少的人前往A市，从而达到每个城市有N人的目标。虽然一开始难以想到贪心解法，但最终理解并实现了解题思路。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

两地调度
公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。

返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。

示例：

输入：[[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 A 市，费用为 10。
第二个人去 A 市，费用为 30。
第三个人去 B 市，费用为 50。
第四个人去 B 市，费用为 20。

最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。

提示：

1 <= costs.length <= 100
costs.length 为偶数
1 <= costs[i][0], costs[i][1] <= 1000
通过次数12,603提交次数19,943

有时候就在想，跟着力扣的标题来做题，明明也看到了是贪心的标签，但就是想不到该怎么贪心，实在是让人感到挫败啊

这道题因为是贪心标签嘛，思考了贪心后总发现，正常的按照A或B的大小来排序显然是很难能得到正确的解法的
于是想要用dp，因为毕竟只有两种状态，去A或者B，那么就dp的去最小值来进行。显然这样可以取到最大或者最小值，但问题是难以做到平分人数

实在难以想出来看了力扣的题解，不得不说，你大爷就是你大爷，人家用的就是贪心，用的我服服帖帖的，人家不仅用贪心了，还非常轻易就写出来，你说这气人不人

好吧言归正传，抱怨归抱怨，还是要学习才是啊，
这道题呢，用的贪心思想是这样的，我们假如让所有人都准备前往B地，那么费用显然是能出来的，但是显然不行，我们需要一半人去A地，那么就从所有人中依次取出人去A地，那么怎么取呢
如果某个人去A地后，这时候公司要花的钱就变成了price【B】-price[A]。我们保证每次这样最小，就能得到正解了

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(),costs.end(),[](const vector<int>&o1,const vector<int>&o2){
            return (o1[0]-o1[1]<o2[0]-o2[1]);
        });
        int total=0;
        int n=costs.size()/2;
        for(int i=0;i<n;i++){
            total+=costs[i][0]+costs[i+n][1];
        }
        return total;
    }
};