Hướng dẫn giải của Giao hàng


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: mrtee

  • Để 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 ~s1~ là tập hợp gồm các nhân viên đang đi tới kho ~1~, ~s2~ là tập các nhân viên đang đi tới kho ~2~, ~s3~ 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;
}