Как указано в предоставленном вами ответе, всегда есть лучшее совпадение, если между двумя совпадениями есть пересечение, когда рост отсортирован для всех мальчиков и всех девочек в порядке возрастания.
Таким образом, возможно решение динамического программирования со сложностью O(n*m).
Итак, у нас есть состояние, представленное двумя индексами, назовем их i и j, где i относится к мальчикам, а j относится к девочкам, тогда в каждом состоянии (i, j) мы можем сделать переход в состояние (i, j+1), т.е. текущий ith мальчик делает не выбирать текущую jth девочку или можно сделать ход в состояние (i+1, j+1), т.е. текущая jth девочка выбирается текущим ith мальчиком и мы выбираем минимум между этими двумя вариантами на каждом уровне.
Это можно легко реализовать с помощью решения DP.
Повторение:
DP[i][j] = minimum(
DP[i+1][j+1] + abs(heightOfBoy[i] - heightofGirl[j]),
DP[i][j+1]
);
Ниже приведен код на С++ для рекурсивного решения DP:
#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
int n, m, htB[100] = {10,10,12,13,16}, htG[100] = {6,7,9,10,11,12,17}, dp[100][100];
int solve(int idx1, int idx2){
if(idx1 == n) return 0;
if(idx2 == m) return INF;
if(dp[idx1][idx2] != -1) return dp[idx1][idx2];
int v1, v2;
//include current
v1 = solve(idx1 + 1, idx2 + 1) + abs(htB[idx1] - htG[idx2]);
//do not include current
v2 = solve(idx1, idx2 + 1);
return dp[idx1][idx2] = min(v1, v2);
}
int main(){
n = 5, m = 7;
sort(htB, htB+n);sort(htG, htG+m);
for(int i = 0;i < 100;i++) for(int j = 0;j < 100;j++) dp[i][j] = -1;
cout << solve(0, 0) << endl;
return 0;
}
Output : 4
Ссылка на решение в Ideone: http://ideone.com/K5FZ9x
Вывод таблицы DP приведенного выше решения:
4 4 4 1000000000 1000000000 1000000000 1000000000
-1 3 3 3 1000000000 1000000000 1000000000
-1 -1 3 3 3 1000000000 1000000000
-1 -1 -1 2 2 2 1000000000
-1 -1 -1 -1 1 1 1
Ответ хранится в состоянии DP[0][0].
person
uSeemSurprised
schedule
31.03.2016
