Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 895 Accepted Submission(s): 246
题解:
输入n个男生,m个女生的身高。
把人数较少的一方和另外一方匹配完,求最少的差值。
分别把男女的身高排序。人数较少的一方的每个人可以匹配abs(m-n+1)个人。
因为|m-n|<=100 所以一个人最多匹配100人。
之后用二维滚动数组就可以了。
dp[i][j]男对女相错j个人的最小身高差;
dp[i%2][k]=min(dp[(i-1)%2][k]+abs(a[i]-b[j]),dp[i%2][k-1])
不知道为啥sort一直错qsort就对了。。。
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; const int INF=0x3f3f3f3f; #define mem(x,y) memset(x,y,sizeof(x)) #define SI(x) scanf("%d",&x) #define PI(x) printf("%d",x) #define SD(x) scanf("%lf",&x) #define P_ printf(" ") typedef long long LL; const int MAXN=10010; double dp[2][110],a[MAXN],b[MAXN]; int cmp(const void *a,const void *b) { return *(double *)a < *(double *)b ? 1 : -1; } int main(){ int n,m; while(~scanf("%d%d",&n,&m),n||m){ if(n<=m){ for(int i=1;i<=n;i++)SD(a[i]); for(int i=1;i<=m;i++)SD(b[i]); } else{ swap(n,m); for(int i=1;i<=m;i++)SD(b[i]); for(int i=1;i<=n;i++)SD(a[i]); } qsort(a+1,n,sizeof(a[1]),cmp); qsort(b+1,m,sizeof(b[1]),cmp); int len=m-n+1; mem(dp,0); for(int i=1;i<=n;i++){ dp[i%2][1]=dp[(i-1)%2][1]+abs(a[i]-b[i]); for(int k=2;k<=len;k++){ int j=i+k-1; dp[i%2][k]=min(dp[(i-1)%2][k]+abs(a[i]-b[j]),dp[i%2][k-1]); } } printf("%.6lf\n",dp[n%2][len]); } return 0; }
原文:http://www.cnblogs.com/handsomecui/p/5204685.html