Pie

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 793 Accepted Submission(s): 214

Problem Description

A lot of boys and girls come to our company to pie friends. After we get their information, we need give each of them an advice for help. We know everyone’s height, and we believe that the less difference of a girl and a boy has, the better it is. We need to find as more matches as possible, but the total difference of the matches must be minimum.

Input

The input consists of multiple test cases. The first line of each test case contains two integers, n, m (0 < n, m <= 10000), which are the number of boys and the number of girls. The next line contains n float numbers, indicating the height of each boy. The last line of each test case contains m float numbers, indicating the height of each girl. You can assume that |n – m| <= 100 because we believe that there is no need to do with that if |n – m| > 100. All of the values of the height are between 1.5 and 2.0.
The last case is followed by a single line containing two zeros, which means the end of the input.

Output

Output the minimum total difference of the height. Please take it with six fractional digits.

Sample Input

2 3
1.5 2.0
1.5 1.7 2.0
0 0

Sample Output

0.000000

Author

momodi@whu

Source

The 5th Guangting Cup Central China Invitational Programming Contest

思路：dp+滚动数组

（1）：要求最佳匹配。首先得将两数组从小到大排序~

（2）：然后再明白dp[][]表示的意思;dp[i][j] 表示a数组中前i个数和b数组中前j个数匹配的最优解

（3）：接下来看看状态转移方程； if(i==j)dp[i][j]=dp[i-1][j-1]+fabs(a[i]-b[j]);

else dp[i][j]=min(dp[i-1][j-1]+fabs(a[i]-b[i]),dp[i][j-1]);

(4): 由于题目中的n最大取到10000。假设开个数组dp[10000][10000],那么执行不了~那么再观察观察状态转移方程，发现当前这个数是由它左边这列递推过来的。我们能够用一个dp[2][10000]的滚动数组就可以，由于我仅仅关心最后一个dp[n][m]值，所曾经面的一些值被覆盖不影响我后面的求值过程；（能够在纸上画一画，就知道这个滚动数组了）

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cmath>
const int maxn=11000;
using namespace std;

double a[maxn],b[maxn];
double dp[2][maxn];

int main()
{
 int n,m;
 while(cin>>n>>m)
 {
        if(n==0&&m==0)break;
        for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
        for(int i=1;i<=m;i++)scanf("%lf",&b[i]);

        double *A=a,*B=b;
        if(n>m){swap(n,m);swap(A,B);}
        sort(A+1,A+1+n);
        sort(B+1,B+1+m);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
         for(int j=i;j<=i+m-n;j++)
         {
          if(i==j)
          {
              dp[i&1][j]=dp[(i-1)&1][j-1]+fabs(A[i]-B[j]);
              //printf("dp[%d][%d] :%.6lf",i,j,dp[i&1][j]);
          }
          else
          {
              dp[i&1][j]=min(dp[(i-1)&1][j-1]+fabs(A[i]-B[j]),dp[i&1][j-1]);
              //printf("dp[%d][%d] :%.6lf",i,j,dp[i&1][j]);
          }
         }
       printf("%.6lf
",dp[n&1][m]);
 }
 return 0;
}