• Để giải được bài toán này, ta sẽ áp dụng thuật toán tham lam.

• Nhận thấy rằng, ta có thể chia bài toán ra thành hai pha riêng biệt. Pha đầu tiên ta sẽ chọn ~x~ nhân viên vào kho ~1~ và ~t-x~ người vào kho hai. Sau đó sẽ tối ưu cách giao hàng tới các địa điểm và lấy ~min~ kết quả.

• Vậy ta có thể thực hiện các pha này như thế nào?
• Gọi tập ~a~ là tập hợp gồm các nhân viên đang đi tới kho ~1~, ~b~ là tập các nhân viên đang đi tới kho ~2~, ~c~ là tập các nhân viên đang không được giao việc.
• Đầu tiên, ta sẽ chọn ~t~ nhân viên đi tới kho ~1~, và từ kho ~1~ sẽ giao tới ~t~ địa điểm nhận hàng. Gọi giá trị ~cur~ là chi phí cho sự lựa chọn này. Gán biến kết quả ~res = cur~.
• Gọi ~a[i] = (x,y)~ là khoảng cách nhân viên ~i~ tới kho ~1~ và kho ~2~.
• Ta ~sort~ các ~a[i]~ theo ~x~ tăng dần.
• Gọi ~b[i] = (x,y)~ là khoảng cách địa điểm ~i~ tới kho ~1~ và kho ~2~.
• Ta ~sort~ các giá trị ~b[i]~ theo ~(y-x)~ tăng dần.
• Từ giờ, ta sẽ dần dần chuyển một nhân viên vào kho ~2~, giảm một nhân viên tới kho ~1~ và hủy một đơn hàng giao từ kho ~1~ thành giao từ kho ~2~, và tính lại khoảng cách quãng đường.
• Ta sẽ ~for~ ~i~ trong khoảng ~[1,t]~, mỗi bước ta có hai lựa chọn:
  • Chuyển một nhân viên từ tập ~s1~ sang ~s3~ và một nhân viên từ ~s3~ sang ~s2~:
    • Để chuyển tối ưu, ta sẽ lấy nhân viên có giá trị ~q = a[i].x~ lớn nhất trong tập ~a~ để chuyển sang ~c~, và lấy nhân viên có giá trị ~p = a[i].y~ nhỏ nhất trong tập ~c~ để chuyển sang ~b~.
    • Độ tăng giá trị của lựa chọn này sẽ là ~(p-q)~.
  • Chuyển một nhân viên từ tập ~s1~ sang tập ~s2~:
    • Để chuyển tối ưu, ta sẽ lấy nhân viên có giá trị ~(a[i].y - a[i].x)~ nhỏ nhất để chuyển.
    • Độ tăng giá trị của lựa chọn này sẽ là ~(a[i].y - a[i].x)~.
  • Ta sẽ xem xét lựa chọn nào là tối ưu nhất về đương đi trong hai lựa chọn trên.
  • Gọi ~\Delta = ~ chi phí tăng lên nhỏ nhất trong hai lựa chọn, vậy lúc này tổng chi phí sẽ là:
    • ~cur += \Delta~ (chi phí chuyển một nhân viên tới kho ~2~ và giảm một nhân viên tới kho ~1~).
    • ~cur += b[i].y - b[i].x~ (chi phí hủy một đơn hàng giao tới địa điểm ~i~ từ kho ~1~ và chuyển thành giao từ kho ~2~).
  • Ta sẽ cập nhất ~res = min (res,cur)~ cho kết quả.
• Để xử lý các thao tác một cách nhanh nhất, ta cần:
  • Nhận thấy tập ~b~ không cần quan tâm do ta không lấy giá trị ra từ nó, vậy nên ta không cần kiểm soát tập này.
  • Tập ~a~ ta sẽ lưu bằng hai ~set~ như sau:
    • ~set~ đầu tiên ~sort~ theo thứ tự tăng dần của ~a[i].x~. (phục vụ lựa chọn một)
    • ~set~ thứ hai ~sort~ theo thứ tự tăng dần của ~a[i].y-a[i].x~. (phục vụ lựa chọn hai)
  • Tập ~c~ ta chỉ cần lưu bằng một ~set~ ~sort~ theo ~a[i].y~ tăng dần.
  • Lúc này những thao tác tìm ~x~ lớn nhất, ~y~ bé nhất, ~y-x~ bé nhất, xóa phần tử khỏi tập và thêm phần tử vào tập chỉ mất ~O(log)~ mỗi lần.
• Độ phức tạp; ~O(n*log)~.

Code C++

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e16;
const int maxN = 1e5 + 5;
struct val {
    int x, y;
};
int n, t;
val a[maxN];
val b[maxN];
struct cmpx {
    bool operator () (const val& a, const val& b) const {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    }
};
struct cmpy {
    bool operator () (const val& a, const val& b) const {
        if (a.y != b.y) return a.y < b.y;
        return a.x < b.x;
    }
};
struct cmpxy {
    bool operator () (const val& a, const val& b) const {
        if (a.y - a.x != b.y - b.x) return a.y - a.x < b.y - b.x;
        return a.y < b.y;
    }
};

signed main() {
    freopen("GH.INP", "r", stdin);
    freopen("GH.OUT", "w", stdout);
    cin >> n >> t;
    for (int i = 1; i <= n; i++) cin >> a[i].x;
    for (int i = 1; i <= n; i++) cin >> a[i].y;
    for (int i = 1; i <= t; i++) cin >> b[i].x;
    for (int i = 1; i <= t; i++) cin >> b[i].y;

    int ans = INF;
    int cur = 0;

    sort(a + 1, a + 1 + n, cmpx());
    multiset<val, cmpx> sx;
    multiset<val, cmpxy> sxy;
    multiset<val, cmpy> sy;

    for (int i = 1; i <= t; i++) {
        sx.insert(a[i]);
        sxy.insert(a[i]);
        cur += a[i].x;
    }
    for (int i = t + 1; i <= n; i++) 
        sy.insert(a[i]);

    sort(b + 1, b + 1 + t, cmpxy());
    for (int i = 1; i <= t; i++)
        cur += b[i].x;

    ans = min(ans, cur);
    for (int i = 1; i <= t; i++) {
        int s1 = sy.empty() ? INF : sy.begin()->y - sx.rbegin()->x;
        int s2 = sxy.begin()->y - sxy.begin()->x;
        if (s1 < s2) {
            val tmp = *sx.rbegin();
            sy.erase(sy.begin());
            sx.erase(sx.find(tmp));
            sxy.erase(sxy.find(tmp));
            sy.insert(tmp);
        }
        else {
            val tmp = *sxy.begin();
            sx.erase(sx.find(tmp));
            sxy.erase(sxy.find(tmp));
        }
        cur += min(s1, s2);
        cur += b[i].y - b[i].x;
        ans = min(ans, cur);
    }
    cout << ans;
}