Bài toán
Cho hai dãy số a và b có n phần tử, dãy a không có hai phần tử giống nhau, dãy b cũng không có hai phần tử giống nhau, tuy nhiên cõ những phần tử xuất hiện ở cả a và b. Tìm cách ghép mỗi phần tử ở a với đúng một phần tử ở b sao cho chi phí là thấp nhất và không được phép nối hai phần tử bằng nhau với nhau. Phần tử nào của a hay b cũng phải được nối, và chỉ nối đúng với một phần tử khác. Chi phí để nối hai phần tử là trị tuyệt đối chênh lệch của chúng. Tổng chi phí đạt được là tổng của các chi phí mỗi phép nối.
Độ phức tạp
O(n)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
using namespace std;
#define long long long
long cost(long x, long y){ if (x==y) return 0x1111222233334444LL; else return x>y?x-y:y-x; }
bool minimize(long &a, long b){ if (a>b) a=b; else return false; return true; }
long buffalo(long a[], long b[], int k){
long r = 0x1111222233334444LL;
if (k==1) {
minimize(r, cost(a[1], b[1]));
}
if (k==2) {
minimize(r, cost(a[1], b[1]) + cost(a[2], b[2]));
minimize(r, cost(a[1], b[2]) + cost(a[2], b[1]));
}
if (k==3) {
minimize(r, cost(a[1], b[1]) + cost(a[2], b[2]) + cost(a[3], b[3]));
minimize(r, cost(a[1], b[1]) + cost(a[2], b[3]) + cost(a[3], b[2]));
minimize(r, cost(a[1], b[2]) + cost(a[2], b[1]) + cost(a[3], b[3]));
minimize(r, cost(a[1], b[2]) + cost(a[2], b[3]) + cost(a[3], b[1]));
minimize(r, cost(a[1], b[3]) + cost(a[2], b[1]) + cost(a[3], b[2]));
minimize(r, cost(a[1], b[3]) + cost(a[2], b[2]) + cost(a[3], b[1]));
}
return r;
}
int n;
long a[1230997];
long b[1230997];
long F[1230997]; // +
long f(int n){
if (n==0) return 0;
long r = 0x1111222233334444LL;
if (F[n]) return F[n];
for (int k=1; k<=3 && k<=n; k++)
minimize(r, f(n-k) + buffalo(a+n-k, b+n-k, k));
return F[n]=r;
}
main(){
int i;
scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%lld%lld", &a[i], &b[i]);
sort(a+1, a+n+1);
sort(b+1, b+n+1);
for (i=1; i<=n; i+=100) f(i);
printf("%lld\n", f(n));
}
Nhận xét