LeetCoe-1029. 两地调度

深藏阁楼爱情的钟 2022-02-15 10:15 234阅读 0赞

# [1029. 两地调度][1029.] #

公司计划面试 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.  1 <= costs.length <= 100
2.  costs.length 为偶数
3.  1 <= costs\[i\]\[0\], costs\[i\]\[1\] <= 1000

### 贪心 ###

这题巧妙，根据两地的价格之差进行排序，前n个人去A，后n个人去B。

class Solution { 
    public:
        int twoCitySchedCost(vector<vector<int>>& costs) { 
            int res = 0;
            sort(costs.begin(),costs.end(),[](const vector<int> a,const vector<int> b){ 
                return a[0]-a[1]<b[0]-b[1];
            });
            for(int i = 0,j = costs.size()-1;i<j;i++,j--)
            { 
                res+=costs[i][0]+costs[j][1];
            }
            return res;
        }
    };

### 动态规划 ###

class Solution { 
    public:
        int twoCitySchedCost(vector<vector<int>>& costs) { 
            int n = costs.size();
            vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX / 2));
            dp[0][0] = 0;
            for (int i = 1; i <= n; ++i) {       
                dp[i][0] = dp[i - 1][0] + costs[i - 1][1];
                for (int j = 1; j <= i; ++j)
                    dp[i][j] = min(dp[i - 1][j - 1] + costs[i - 1][0], 
                           dp[i - 1][j] + costs[i - 1][1]);
            }
            return dp[n][n / 2];
        }
    };

[1029.]: https://leetcode-cn.com/problems/two-city-scheduling/

发表评论取消回复

表情：

评论列表（有 0 条评论，234人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCoed 2, 23, 25, 112, 113

文章目录 1. 两数相加 2. K 个一组翻转链表 3. 合并 K 个升序链表 4. 路径总和I 5. 路径总和II 1. 两数相加

绝地灬酷狼/ 2023年09月27日 19:18/ 0 赞/ 92 阅读

相关 leetcode 1029 两地调度

公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs\[i\]\[0\]，飞往 B 市的费用为 costs\[i\]\[1\]。返回将每个人都飞到某座城市的最

缺乏、安全感/ 2023年05月31日 12:03/ 0 赞/ 12 阅读

相关两地调度[1029]

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

偏执的太偏执、/ 2023年02月24日 08:48/ 0 赞/ 159 阅读

相关两地三中心

1、两地三中心同城双中心+异地灾备中心， “两地三中心”的灾备模式，方案兼具高可用性和灾难备份的能力。 1. 同城双中心

曾经终败给现在/ 2023年02月23日 08:41/ 0 赞/ 10 阅读

相关 leetcoe253 最少会议室问题

题目：有一堆会议，每个会议都有开始时间和结束时间，问至少需要几个房间可以安排下这些会议？该问题可以使用贪心来做，使用小顶堆来实现最简单。首先用一个最小堆来将会议按照会

秒速五厘米/ 2022年09月11日 00:04/ 0 赞/ 182 阅读

相关 sicily 1029

思路：首先创建两个函数operate() 和cycle()，其中operate()求得两个大数之和，cycle()将数组向后平移一位。首先初始化数组num，数组num存储兔子的

素颜马尾好姑娘i/ 2022年08月06日 08:12/ 0 赞/ 163 阅读

相关 PAT乙级1029

1029 旧键盘（20 分）旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。

今天药忘吃喽~/ 2022年05月11日 00:56/ 0 赞/ 192 阅读

相关 LeetCoe-1029. 两地调度

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

深藏阁楼爱情的钟/ 2022年02月15日 10:15/ 0 赞/ 235 阅读

相关 leetcode1029

1 class Solution(object): 2 def twoCitySchedCost(self, costs: 'List[List[in

淩亂°似流年/ 2021年12月19日 04:09/ 0 赞/ 155 阅读

相关 URAL 1029

题目大意：M层N列的矩阵（各元素均为正整数），找出一个路径从第一层到达第M层，使得路径上的所有数的和是所有可达路径中最小的，每次上到下一层以后就不能再上去，依次输出路径上的各点

清疚/ 2021年12月14日 00:45/ 0 赞/ 252 阅读