Editorial for Chuyến xe cuối ngày

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gợi ý 1 - Tách những người ở hai phía kho

Mọi hành trình bắt đầu tại tọa độ 0. Hãy gom người nhận quà ở bên trái và bên phải thành hai danh sách khoảng cách đến kho. Chi phí của một chuyến chỉ phụ thuộc vào người xa kho nhất trong chuyến đó.

Gợi ý 2 - Gom mỗi K người xa nhất thành một chuyến

Trên mỗi phía, sắp xếp khoảng cách giảm dần. Một chuyến phục vụ tối đa K người; nếu phải quay về kho thì chuyến có người xa nhất ở khoảng cách d tốn 2d.

Chỉ chuyến cuối không cần quay lại. Hãy chọn chuyến có người xa kho nhất làm chuyến cuối để tiết kiệm nhiều nhất.

Lời giải đầy đủ

Gom chuyến trên từng phía

Với một phía, sắp các khoảng cách theo thứ tự giảm dần và chia liên tiếp thành từng nhóm tối đa K người. Nhóm bắt đầu tại vị trí i có người xa nhất cách kho d_i; nếu chuyến quay về kho, quãng đường là 2d_i.

Có thể xem các chuyến đi hai phía riêng biệt: một chuyến ghé cả hai phía rồi quay về có quãng đường bằng tổng hai lượt đi-về riêng. Nếu chuyến cuối ghé cả hai phía và kết thúc ở một phía, quãng đường cũng bằng một lượt đi-về ở phía kia cộng với lượt đi một chiều ở phía kết thúc. Vì vậy, việc trộn hai phía không làm giảm tổng quãng đường tốt nhất.

Tính tổng quãng đường nếu mọi chuyến đều quay về kho. Trong các nhóm, nhóm xa kho nhất có thể là chuyến cuối; bỏ phần quay về của nhóm đó, tức trừ đi khoảng cách xa nhất.

Độ phức tạp
  • Thời gian: O(N \log N), do sắp xếp.
  • Bộ nhớ: O(N).
Code C++17
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<long long> leftSide, rightSide;
    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        if (x < 0) leftSide.push_back(-x);
        else rightSide.push_back(x);
    }

    sort(leftSide.rbegin(), leftSide.rend());
    sort(rightSide.rbegin(), rightSide.rend());

    long long roundTripDistance = 0;
    long long farthestGroup = 0;

    auto processSide = [&](const vector<long long>& distances) {
        for (int i = 0; i < (int)distances.size(); i += k) {
            roundTripDistance += 2 * distances[i];
            farthestGroup = max(farthestGroup, distances[i]);
        }
    };

    processSide(leftSide);
    processSide(rightSide);

    cout << roundTripDistance - farthestGroup << '\n';
    return 0;
}

Loading...