舞蹈对算法(来自编程竞赛)

Question

问题如下:投入：

3 10

1 2 3

12 11 101

其中3(n)是男孩的数目，10(k)是接受的身高差，接下来的2行分别是女孩和男孩的身高。

12，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 hashMaps --一个键是男孩，值是女孩可以跳舞的女孩列表，另一个哈希图是女孩和值的男孩，他们可以跳with.The，最小的两个哈希映射是formed.This通过这个基本测试用例的最大对，但是所有其他cases.Want都不知道我的算法不能工作的情况，如果可能的话，这个问题的其他解决方案。

Answer 1

这个问题可以用双指针方法很容易地解决.

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

给定两个按升序排列的数组(A和B)和整数X。我们需要找到i和j，这样ai + bj等于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++;
}

在这里，我们可以使用贪婪的approach.In这个问题，我们需要对两个高度数组进行排序。我们有两个指数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，则在给定图中的最大二部匹配将是我们的答案。

Answer 2

假设男孩和女孩要么是矮的，要么是高的，而唯一有效的配对是矮个子和高个子。如果有10个矮小的女孩，一个矮小的男孩，一个高的女孩，10个高的男孩，那么矮小的男孩和一个矮小的女孩跳舞，高个的女孩和一个高个男孩跳舞，没有其他人跳舞，总共有2对，而所有的11个女孩和所有的11个男孩都有他们可以跳舞的人，所以你的算法返回11。