2

SPOJ の質問:

との間の正数の2 つの配列 と が与えられAます。差の絶対値の合計が最小になるように、各整数を整数とペアにする必要があります。それぞれ最大 5000 個の整数を含めることができます。B11,000,000aAbBAB

例えば：

A=[10, 15, 13]とB=[14,13, 12]の場合、最良のペアリングはと(10, 12)で(15, 14)あり、(13, 13)これは私|10-12|+|15-14|+|13-13|=3たちが達成できる最小のものです。したがって、達成される最小合計は です3。

動的プログラミングの質問だと思います。

編集：

配列のサイズは異なる場合がありますが、それぞれ最大 5000 個の要素を含めることができます。

私のコード:

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

static int DP[5002][5002], N, M, tmp;
vector<int> B, C;

int main()
{
    scanf("%d %d", &N, &M); memset(DP, -1, sizeof DP);
    B.push_back(0); C.push_back(0); DP[0][0]=0;
    for(int i=1; i<=N; ++i){scanf("%d", &tmp); B.push_back(tmp);} \\inputting numbers.
    for(int i=1; i<=M; ++i){scanf("%d", &tmp); C.push_back(tmp);}
    sort(B.begin(), B.end()); sort(C.begin(), C.end());         \\Sorting the two arrays.

    if(C.size()<=B.size()){                         \\Deciding whether two swap the order of arrays.
        for(int i=1; i<=N; ++i){
            for(int j=1; j<=M; ++j){
                if(j>i)break;
                if(j==1)DP[i][j]=abs(C[j]-B[i]);
                else{
                    tmp=DP[i-1][j-1]+abs(C[j]-B[i]);
                    DP[i][j]=(DP[i-1][j]!=-1)? min(tmp, DP[i-1][j]): tmp;
                }
            }
        }
        printf("%d\n", DP[N][M]);    \\Outputting the final result.
    }
    else{
        for(int i=1; i<=M; ++i){
            for(int j=1; j<=N; ++j){
                if(j>i) break;
                if(j==1)DP[i][j]=abs(C[i]-B[j]);
                else{
                    tmp=DP[i-1][j-1]+abs(C[i]-B[j]);
                    DP[i][j]=(DP[i-1][j]!=-1)? min(tmp, DP[i-1][j]): tmp;
                }
            }
        }
        printf("%d\n", DP[M][N]);
    }
    return 0;
}
4

1 に答える 1

3

Niels のコメントは、配列が同じサイズである場合、それらを並べ替えて値をペアにする必要があることを明らかにしています。それに基づいて、一般的なケースを構築できます。

arr1最初の配列の長さは、2 番目の長さ以下であると仮定しますarr2。そうでない場合は、それらを交換してください。まず、両方の配列を並べ替えdp[A][B]、部分配列のみを考慮したときの最小の差を としますarr1[A...](arr2[B...]つまり、前方arr1から最後まで)。次の 2 つの選択肢があります。Aarr2B

  • と をペアリングAしBます。この場合、合計で の差が生じます|arr1[A]-arr2[B]| + dp[A+1][B+1]。

  • 使用しないでくださいB。この場合、二度と考慮Bしないことに注意してください (なぜなら、AとBを異なる要素にペアリングすると、両方のペアを交換でき、合計が下がるからです)。したがって、単に無視することができB、答えは になりますdp[A][B+1]。

基本ケースはかなり明白なはずです。

  • dp[length of arr1][length of arr2] = 0
  • dp[A][length of arr2] = infinity( の残りの要素をペアにすることはできませんarr1)。
于 2013-05-21T04:48:58.733 に答える