1029. Two City Scheduling (双城面试2N人费用最小问题)
There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].
Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.
Example 1:
Input: [[10,20],[30,200],[400,50],[30,20]] Output: 110 Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20. The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
Note:
1 <= costs.length <= 100- It is guaranteed that
costs.lengthis even.1 <= costs[i][0], costs[i][1] <= 1000
以上是原题描述。
现在来说一下我的算法：
- 从每个数对中选择较小的那个，选完后分成了a、b两列
- 看a和b谁更多，计算出多的一方需要补偿给对方几个（n）
- 计算多的一列中的数字在原来数对中的差值，选择前n个差值最小的数对，进行替换
比如上面的例子，第一步后，a列：259；b列：54，667，139，118，469.
第二步：a列1个，b列5个，相差4个，b需要补给a列2个。
第三步：计算出新的差值列：394，259，45，722，108. 发现最小的2个是45和108，对应的是184替换139，577替换469.（见下图）
最终我们选择的数字是：259，54，667，184，139，118，577.
和为1859.
代码：
1 class Solution { 2 public: 3 int twoCitySchedCost(vector<vector<int>>& costs) { 4 int result=0; 5 vector<vector<int>> a;//左列 6 vector<vector<int>> b;//右列 7 vector<int> c; //辅助 8 vector<vector<int>> d;//差值 9 int diff; 10 11 //初始分选，每个数对选最小的那个 12 for (auto iter = costs.begin(); iter != costs.end(); iter++) 13 { 14 if((*iter)[0]>(*iter)[1]) { 15 c.push_back((*iter)[1]); 16 c.push_back(iter-costs.begin());//返回原始数组的第一维下标 17 b.push_back(c); 18 } 19 else{ 20 c.push_back((*iter)[0]); 21 c.push_back(iter-costs.begin());//返回原始数组的第一维下标 22 a.push_back(c); 23 } 24 c.clear(); 25 } 26 27 diff=a.size()-b.size();//a比b多几个 28 if(diff==0){ 29 for (auto iter = a.begin(); iter != a.end(); iter++) 30 result+=(*iter)[0] ; 31 32 for (auto iter = b.begin(); iter != b.end(); iter++) 33 result+=(*iter)[0] ; 34 } 35 else if(diff > 0){//a>b 36 diff = diff/2;//2N人一定能整除 37 for (auto iter = a.begin(); iter != a.end(); iter++) 38 { 39 int index=(*iter)[1]; 40 c.push_back(abs(costs[index][0]-costs[index][1])); 41 c.push_back(index); 42 d.push_back(c); 43 c.clear(); 44 } 45 for (auto iter = b.begin(); iter != b.end(); iter++) 46 result+=(*iter)[0] ; 47 while(diff-->0){ 48 int index = smallest(d);//注意这里 49 for (auto iter = a.begin(); iter != a.end(); iter++) 50 { 51 if((*iter)[1]==index) 52 (*iter)[0]=costs[(*iter)[1]][1];//注意第二个下标是1 53 } 54 } 55 for (auto iter = a.begin(); iter != a.end(); iter++) 56 result+=(*iter)[0] ; 57 } 58 else{//diff<0 59 //a<b 60 diff=0-diff; 61 diff = diff/2; 62 for (auto iter = b.begin(); iter != b.end(); iter++) 63 { 64 int index=(*iter)[1]; 65 c.push_back(abs(costs[index][0]-costs[index][1])); 66 c.push_back(index);//返回原始数组的第一维下标 67 d.push_back(c); 68 c.clear(); 69 } 70 for (auto iter = a.begin(); iter != a.end(); iter++) 71 result+=(*iter)[0] ; 72 while(diff>0){ 73 int index = smallest(d);//注意这里 74 for (auto iter = b.begin(); iter != b.end(); iter++) 75 { 76 if((*iter)[1]==index){ 77 (*iter)[0]=costs[(*iter)[1]][0];//注意第二个下标是0 78 diff--; 79 } 80 81 82 } 83 } 84 85 for (auto iter = b.begin(); iter !=b.end(); iter++) 86 result+=(*iter)[0] ; 87 } 88 89 return result; 90 } 91 92 int smallest(vector<vector<int>>& hahaha){ 93 vector<int> c; 94 for (auto iter = hahaha.begin(); iter != hahaha.end(); iter++) 95 c.push_back((*iter)[0]); 96 auto smallest=min_element(begin(c),end(c)); 97 int index = hahaha[distance(begin(c),smallest)][1]; 98 hahaha[distance(begin(c),smallest)][0]=1000; 99 return index; 100 } 101 };
本地测试用的主函数：
1 int main() { 2 Solution* mySo = new Solution(); 3 vector<vector<int>> cos = { {259,770},{448,54},{926,667},{184,139},{840,118},{577,469} }; 4 cout << mySo->twoCitySchedCost(cos) << endl; 5 }
注：这道题难度是easy·········