TRAKA – spoj

Đề bài:

Tóm tắt đề

Có N người thợ, M chiếc xe. Người thứ i hoàn thành việc sửa bộ phận xe mình phụ trách với tốc độ T[i]. Xe thứ j có độ rắc rối là F[j]. Thời gian người thứ i cửa xong bộ phận người i phụ trách trên xe j trong thời gian T[i] * F[j]. Các công việc được thực hiện theo thứ tự từ người 1 -> n. Người i làm việc liên tục ko đc dừng lại(tức là sửa xong xe i thì đến xe i + 1). Với mỗi thời điểm t, mỗi chiếc xe chỉ được sửa bởi tối đa 1 người. Tính thời điểm bé nhất để n người sửa xong m chiếc xe.

Dữ Liệu:

  • Dòng đầu gồm 2 số nguyên N (1 <= N <= 100 000) – số người thợ, M (1 <= M <= 100 000) – số chiếc xe cần sửa.
  • Dòng thứ i trong n dòng tiếp theo là T[i] – tốc độ sửa xong bộ phận người i phụ trách.
  • Dòng thứ j trong m dòng tiếp theo là F[j] – độ rắc rối của chiếc xe thứ j.

Kết quả:

  • Gồm 1 dòng là kết quả của bài toán.

Ví dụ:

Input:

3 3
2
1
1
2
1
1

Output:

11

Thuật toán:

Ở bài toán này thì thời điểm kết thúc công việc của người n là kết quả bài toán. Vì mỗi người thợ sẽ làm việc liên tục ko nghỉ nên ta cần tìm thời điểm bắt đầu thực hiện công việc của người n.
Gọi q[i] là tổng độ phức tạp của các chiếc xe từ 1 -> i.

Xét:
Người thứ u bắt đầu công việc từ thời điểm 0, tốc độ C. Thời điểm người u hoàn thành xe i là q[i] * C, hoàn thành xe i + 1 là q[i + 1] * c.
Người thứ v bắt đầu công việc ngay sau u, tốc độ D. Có thời điểm hoàn thành xe i là q[i] * D.
=> Để người v sửa xe i + 1 thì v cần chờ 1 khoảng thời gian là q[i + 1] * C – q[i] * D. Ta cần tìm min(q[i + 1] * C – q[i] * D).
Từ đây, ta để tính được thời điểm bắt đầu làm việc của người n là delta.
Kết quả bài toán là: delta + q[m] * t[n].

Nhận thấy độ phức tạp của thuật toán trâu bò là O(n * m) không đem lại thuật toán đủ tốt để giải bài toán. Nên ta cần tìm cách giảm độ phức tạp xuống.

Vậy, chúng ta nên làm thế nào ?? 😀 ??

Nhìn vào biểu thức q[i + 1] * C – q[i] * D có j đặc biệt ? Đây là biểu thức tích chéo của 2 vector (C; D) * (q[i]; q[i + 1]).

Coi (q[i]; q[i + 1]) là 1 điểm trên mặt phẳng tọa độ Oxy, và ta có vector u = (C; D).
Ta cần tìm điểm A(x, y) sao cho vector OA * u bé nhất. Nhận thấy điểm A cần tìm nằm trên đường lồi.

Trong hình vẽ bên dưới, đường thẳng màu xanh là đường lồi.

traka-yeulaptrinh.pw

Nhận thấy, các điểm trên đường lồi có tích chéo với (C; D) có giá trị theo hình parabol. Đến đây ta có thể áp dụng kĩ thuật chặt nhị phân hoặc tam phân để tìm đỉnh có tích chéo bé nhất.

Độ phức tạp là: O(m * log(n)).

Code:

#include <bits/stdc++.h>
using namespace std;
 
typedef pair <long long, long long> ii;
 
const int N = 1e5 + 10;
 
int n, m, k;
ii A[N], p[N];
long long t[N];
 
ii operator - (ii a, ii b) { return  make_pair(b.first - a.first, b.second - a.second); }
long long operator * (ii a, ii b) { return a.first * b.second - a.second * b.first; }
 
bool cw(ii a, ii b, ii c) { return (b - a) * (c - b) < 0; }
 
void load() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &t[i]);
        t[i] += t[i - 1];
    }
    for (int i = 1; i <= n; ++i)
        A[i] = make_pair(t[i - 1], t[i]);
}
 
void findConvexLine() {
    k = 0;
    p[k++] = make_pair(0, 0);
    for (int i = 1; i <= n; ++i) {
        while (k > 1 && !cw(p[k - 2], p[k - 1], A[i])) k--;
        p[k++] = A[i];
    }
}
 
long long get(int x, int y) {
    //ii v = make_pair(x, y);
    int l = 0, r = k - 2, cur = 0;
    while (l <= r) { // (l - 1) * v <= 0 && (r + 1) * v > 0
        int mid = (l + r) >> 1;
        if ((p[mid + 1].first - p[mid].first) * y <= (p[mid + 1].second - p[mid].second) * x) {
            l = mid + 1;
            cur = l;
        } else {
            r = mid - 1;
        }
    }
    return make_pair(x, y) * p[cur];
}
 
void process() {
    findConvexLine();
    int x = 0, y = 0;
    long long delay = 0;
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &y);
        delay += get(x, y);
      //  cerr << get(x, y) << "\n";
        x = y;
    }
    long long ans = delay + 1ll * t[n] * x;
    printf("%lld\n", ans);
}
 
int main() {
 
    load();
    process();
 
    return 0;
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*