algorithm - SPOJ : DCOWS Why a Greedy algorithm does not work?

Question

提问链接:https://www.spoj.com/problems/DCOWS/

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

给定两个列表 B & C相应尺寸为 N & M与 (M > N) ，分别由公牛和奶牛的高度组成作为这个问题的输入，我解决这个问题的方法如下:

• 对两个列表进行排序 B & C非降序
• 设置k = 0
• 对于 list B 中的每一项 B_i
  • 在 C[k..M-N+i] 上使用改进的二进制搜索在位置 j 找到一个元素 C_j，0<=j<=M-N在 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)。