Codeforces - 1443C - The Delivery Dilemma

★ Today's tune: https://youtu.be/AVDSZXtRgMU

★ Link: https://codeforces.com/contest/1443/problem/C

★ Difficulty: 1400

★ Tags: binary search, greedy

★ Tóm tắt (khuyến khích không nên đọc vì đọc xong sẽ không hiểu):

Petya muốn chuẩn bị N món ăn cho tiệc sinh nhật của hắn. Nhưng N món ăn này phải được đặt từ N nhà hàng khác nhau (người giàu thì làm gì cũng được). Cho dãy a[] và b[], mỗi dãy gồm N phần tử, là thời gian để có được món ăn nếu nhà hàng thứ i vận chuyển (a[i]), hoặc Petya tự đến nhà hàng thứ i lấy và quay về (b[i]). Yêu cầu tính thời gian nhỏ nhất có thể để tất cả món ăn đều được chuyển đến nhà Petya.

Với dãy a[], mỗi nhà hàng sẽ bắt đầu vận chuyển tính từ thời điểm 0 -> thời gian tối đa để các món ăn do nhà hàng vận chuyển đến nơi là max của dãy a[] đã chọn được (max(a1,...)).

Với dãy b[], Petya sẽ lần lượt đến từng nhà hàng để lấy -> thời gian tối đa để các món ăn do Petya tự lấy đến nơi là tổng của dãy b[] đã chọn được (sum(b2,...)).

★ Ý tưởng: ta nghĩ ngay đến việc tìm kiếm nhị phân đáp án. 

Giả sử thời gian cần là x: 

    - Chỉ chọn a[i] nếu a[i] <= x.

    - Chọn b[i] nếu không thể chọn a[i].

Sau đó kiểm tra tổng thời gian có nhỏ hơn hoặc bằng x hay không (tổng thời gian chính là max(max(a1,...), sum(b2,...))). Nếu nhỏ hơn hoặc bằng x thì giảm r, trong trường hợp ngược lại thì tăng l. Các bạn đọc code sẽ rõ.

★ Code: https://ideone.com/5TjG7s