在西部数码做的企业网站不能与阿里巴巴网站相连接/市场营销计划书模板

题意：长度为n的a数组，长度为m的b数组，|n - m| <= 100，然后求得使得个数小的那个数组和个数多的那个数组匹配完，最小的sigma(fabs(a[i] - b[j]))最小。

思路：将两个数组进行排序，然后想要得到的值最小，个数小的a[i]只能和 i到i+ 相差的个数的对应的b[j]相匹配，因为数组不能开很大，所以用到了滚动数组优化

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
#define clr(x,y) memset(x,y,sizeof x)
#define INF 0x3f3f3f3fdouble a[maxn],b[maxn];double dp[2][maxn];
int main()
{int n,m;while( ~ scanf("%d%d",&n,&m)){if(n == 0 && m == 0)break;if(n <= m){for(int i = 1;i <= n;i ++)scanf("%lf",&a[i]); sort(a + 1,a + n + 1);for(int i = 1;i <= m;i ++)scanf("%lf",&b[i]); sort(b + 1,b + m + 1);}else{for(int i = 1;i <= n;i ++)scanf("%lf",&a[i]); sort(a + 1,a + n + 1);for(int i = 1;i <= m;i ++)scanf("%lf",&b[i]); sort(b + 1,b + m + 1);swap(n,m);swap(a,b);}clr(dp,0);for(int i = 1;i <= n;i ++){for(int j = i;j <= i + m - n;j ++){if(i == j){dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + fabs(a[i] - b[j]);}else{dp[i % 2][j] = min(dp[(i - 1) % 2][j - 1] + fabs(a[i] - b[j]),dp[i % 2][j - 1]);}}}printf("%.6f\n",dp[n % 2][m]);}return 0;
}