let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

ACMNB - ACM

problem.md

SuperCoders là đội tuyển huyền thoại của trường XYZ đã nhiều lần vô địch cuộc thi lập trình viên vũ trụ ACM Universe Final. Theo thể thức cuộc thi, mỗi đội tham dự chỉ có đúng 3 thành viên và được giao duy nhất một máy tính, chính vì vậy việc điều phối công việc vô cùng quan trọng. Trong đội SuperCoders, PHUONGHD - đội trưởng - là người nắm giữ vai trò đó.

Đề thi ACM năm nay gồm có 2n bài đánh số từ 1 tới 2n. Bằng kỹ năng thiết kế thuật toán siêu việt, chỉ vài giây sau khi đọc đề, PHUONGHD đã có lời giải cho cả 2n bài. Vấn đề còn lại là phân công hai người còn lại lập trình bởi PHUONGHD không quen với thứ ngôn ngữ lập trình mới được đưa vào sử dụng tại cuộc thi.

Do rất hiểu hai lập trình viên Tí và Tèo trong đội, PHUONGHD biết rằng bài thứ i nếu giao cho Tí làm sẽ mất \(a_i\) giây, cũng bài đó nếu giao cho Tèo sẽ mất \(b_i\) giây để hoàn thành (∀i: 1 ≤ i ≤ 2n). Nhiệm vụ của bạn là hãy giúp PHUONGHD phân công cho hai lập trình viên, mỗi người làm đúng n bài sao cho tổng thời gian lập trình cả 2n bài là ít nhất.

Dữ liệu:

  • Dòng 1 chứa số nguyên dương \(n \le 4 \times 10^5\)
  • \(2n\) dòng tiếp theo, dòng thứ i chứa hai số nguyên dương \(a_i, b_i \le 100\) cách nhau bởi dấu cách.

Kết quả: Ghi ra một số nguyên duy nhất là tổng thời gian lập trình cả \(2n\) bài theo phương án phân công tìm được.

Ví dụ:

INPUT
2
2 1
3 2
5 3
1 2

OUTPUT
8
  • 40% số điểm ứng với các test có \(n \le 1000\)
  • 30% số điểm ứng với các test có \(n \in [10^4, 10^5]\)
  • 30% số điểm ứng với các test có \(n \in [3 \times 10^5, 4 \times 10^5]\)
solution.md

Ban đầu, giao tất cả các công việc cho B làm. Ta có:

\[kq = \sum_{i=1}^{2n} b_i\]

Sau đó, tạo mảng \(c: c_i = a_i - b_i\), với ý nghĩa là nếu chọn A làm công việc i thay cho B thì thời gian cần làm sẽ tăng lên một lượng là \(c_i\) (\(c_i\) có thể âm). Sắp xếp lại mảng \(c\) tăng dần rồi cộng thêm \(n\) phần tử đầu của \(c\) vào kết quả.

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int n;
    cin >> n;
    vector<int> c(2 * n);
    int res = 0;
    for (int &c: c) {
        int a, b;
        cin >> a >> b;
        res += b;
        c = a - b;
    }
    sort(c.begin(), c.end());
    for (int i = 0; i < n; i++) {
        res += c[i];
    }
    cout << res;
    return 0;
}
Comments