java - Dance Pair Algorithm(来自编程竞赛)

Question

问题如下:输入:

3 10

1 2 3

12 11 101

其中 3(n) 是男孩和女孩的数量 10(k) 是可接受的高度差接下来两行分别是女生和男生的高度

1 2 3 是三个男孩的高度

12 11 101是3个女生的高度

现在我们必须找到一对一女孩和一男孩的最大数量使得它们的高度差小于或等于k。

给定:

      K >= 1 and less than 10^9,

      N >=1 and less than 10^5,

      heights(both boy an girl)>=1 and less than 10^9.

一个女孩不能和一个以上的男孩共舞，反之亦然

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
    Map<Integer,List<Integer>> boyGirlsPair= new HashMap<Integer,List<Integer>>();
    Map<Integer,List<Integer>> girlBoysPair= new HashMap<Integer,List<Integer>>();
    int dancingPairsCount = 0;
    int count = 0;
    Scanner scan = new Scanner(System.in);
    int N = scan.nextInt();
    long K = scan.nextLong();
    long[] boysHeightList = new long[N];
    long[]  girlsHeightList = new long[N];
    scan.nextLine();
    while (count<N) {
        boysHeightList[count]=scan.nextLong();
        count++;
    }
    scan.nextLine();
    count =0;
    while (count<N) {
    girlsHeightList[count]=scan.nextLong();
    count++;
    }
    scan.close();
    for (Integer boysHeightListIter =0;boysHeightListIter<N;boysHeightListIter++) {
        for (Integer girlsHeightListIter=0;girlsHeightListIter<N;girlsHeightListIter++) {
            if (Math.abs(boysHeightList[boysHeightListIter] - girlsHeightList[girlsHeightListIter]) <= K) {
                if(boyGirlsPair.containsKey(boysHeightListIter))
                {
                    List<Integer> pairValue = boyGirlsPair.get(boysHeightListIter);
                    pairValue.add(girlsHeightListIter);
                    boyGirlsPair.put(boysHeightListIter,pairValue);
                }
                else
                {
                    List<Integer> pairValue = new ArrayList<Integer>();
                    pairValue.add(girlsHeightListIter);
                    boyGirlsPair.put(boysHeightListIter,pairValue); 
                }
                if(girlBoysPair.containsKey(girlsHeightListIter))
                {
                    List<Integer> pairValue = girlBoysPair.get(girlsHeightListIter);
                    pairValue.add(boysHeightListIter);
                    girlBoysPair.put(girlsHeightListIter,pairValue);
                }
                else
                {
                    List<Integer> pairValue = new ArrayList<Integer>();
                    pairValue.add(boysHeightListIter);
                    girlBoysPair.put(girlsHeightListIter,pairValue);
                }   
            }
        }
    }
   if(girlBoysPair.size()<=boyGirlsPair.size())
   {
       System.out.println(girlBoysPair.size());
   }
   else
   {
       System.out.println(boyGirlsPair.size());
   }
 }
}

我使用的基本算法由 2 个 hashMap 组成，一个以男孩为键，值是可以与之共舞的女孩列表，另一个以女孩为键，值是可以与之共舞的男孩的 hashmap。2 个 HashMap 中最小的是可以形成的最大对数。这通过了比赛的这个基本测试用例，但在所有其他情况下都失败了。想知道我的算法不起作用的一种情况，如果可能的话，还有其他解决方案。

Answer 1

使用两点法可以很容易地解决这个问题。

我会尝试用一个问题的例子来描述这个方法。

给定两个按升序排序的数组(A 和 B)和一个整数 x。我们需要找到 i 和 j，使得 a[i] + b[j] 等于 X。i和j是我们的指针，第一步i指向a的第一个元素，j指向b的最后一个元素。

i = 0; j = b.size() - 1;

在数组a中逐个移动第一个指针，并在需要时修正第二个指针的位置

while (i < a.size())
{
   while(a[i] + b[j] > X && j > 0) j--;
   if (a[i] + b[j] == X) writeAnswer(i, j);
   i++;
}

在这里，我们可以使用贪心的方法。在这个问题中，我们需要对两个高度数组进行排序。我们为男孩保留两个索引 i，为女孩保留 j。

这是一个 C++ 实现-

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;

#define sint long long int

int main() {
    sint n,k;
    cin>>n>>k;
    assert(1<=n && n<= 100000);
    assert(1<=k && k <=1000000000);
    sint a[n];
    sint b[n];
    for(sint i =0 ; i< n  ; i++)
    {
            cin>>a[i];
            assert(1<=a[i] && a[i] <=1000000000);
    }
    for(sint i =0 ; i< n ; i++)
    {
            cin>>b[i];
            assert(1<=b[i] && b[i] <=1000000000);
    }
    sint i = 0;
    sint j = 0;
    sort(a,a+n);
    sort(b,b+n);
    sint value = 0;
    while(i < n && j < n)
    {
        if(abs(a[i] - b[j]) <= k)
        {
            i++;
            j++;
            value++;
        }
        else if(a[i] < b[j])
            i++;
        else
            j++;
    }
    cout<<value<<endl;
    return 0;
}

我们还讨论一个 O(N^2) 方法来解决这个问题-

创建一个二部图，两个部分都包含 N 个顶点。在第一部分中，每个顶点将代表一个男孩。同样，第二部分中的每个顶点都代表一个女孩。现在，如果一对男孩和女孩的高度差小于或等于 K，则他们之间将存在一条边。给定图中的最大二分匹配将是我们的答案。