SPOJ：DCOWS 为什么贪心算法不起作用？

Question

问题Link：https://www.spoj.com/problems/DCOWS/

我想弄清楚为什么我解决上述问题的贪婪方法不起作用。

给定两个列表 B & C，对应大小 N & M 和 (M > N)，分别由公牛和奶牛的身高组成这个问题的输入，我解决这个问题的方法如下：

• 按非降序对两个列表 B 和 C 进行排序
• 设置k = 0
• 对于 B_i list B 中的每个项目
  • 在 C[k..M-N+i] 上使用修改后的二进制搜索在位置 j[= 找到一个元素 C_j 55=], 0<=j<=M-N in list C 与 B_i
  的绝对差最小
  • 加abs(B_i - C_j) 到结果
  • 为循环的下一次迭代更新k = j + 1

代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int my_bsearch(long *arr, int lo, int hi, long x)
{
    int mid = lo + (hi - lo)/2;
    if (lo == mid)
    {
        if (abs(x - arr[lo]) <= abs(x - arr[hi])) return lo;
        else                  return hi;
    }

    if ((mid-1 >= 0) && (abs(x - arr[mid-1]) <= abs(x - arr[mid])))
        return my_bsearch(arr, lo, mid, x);
    else
        return my_bsearch(arr, mid, hi, x);
}

int main() {
    int M, N;
    cin >> N >> M;

    long bulls[N], cows[M];
    for (int i=0; i<N; i++) cin >> bulls[i];
    for (int i=0; i<M; i++) cin >> cows[i];

    sort(bulls, bulls + N);
    sort(cows, cows + M);

    long long min_val = 0, lo = 0, hi = M-N;
    for (int i=0; i<N; i++) {
        lo = my_bsearch(cows, lo, hi, bulls[i]);
        min_val += abs(bulls[i] - cows[lo]);
        lo++, hi++;
    }
    cout<< min_val << endl;

    return 0;
} 

Answer 1

正如这个类似问题 Can we solve the “printing neatly” problem using a greedy algorithm 中所述，贪婪的解决方案通常会误入歧途。考虑以下数据：

公牛队：5、5

奶牛：1、6、15

您的算法输出的最小距离为 11（对 5 到 6，然后 5 到 15）。但最佳解决方案显然是 5（配对 5 对 1，以及 5 对 6）。