ACM

Points: 0.40 (partial)

Time limit: 1.0s

Memory limit: 512M

Input: stdin

Output: stdout

Problem source:

PreVNOI 2013 Day 1, Problem 1, Thầy Hồ Ðắc Phương

Problem type

Allowed languages

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 ~(\forall i: 1 \leq i \leq 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.

Input

Dòng ~1~ chứa số nguyên dương ~n \leq 4\cdot 10^{5}~

~2n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~a_i~, ~b_i \leq 100~ cách nhau bởi dấu cách

Output

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.

Giới hạn

~40\%~ số điểm ứng với các test có ~n \leq 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\cdot 10^{5}~, ~4\cdot 10^{5}]~

Sample Input

Sample Output

Note

Đề gốc PREVOI 2013:

Comments

Please read the guidelines before commenting.

-7

zatarainbow commented on July 13, 2024, 2:50 p.m.

include <bits/stdc++.h>

using namespace std; int main() { iosbase::syncwith_stdio(false); cin.tie(NULL); int n; cin >> n; int sum = 0; int* ptr = new int[2n]; int i = 0; while(i < 2n) { int a,b; cin >> a >> b; sum += a; ptr[i++] = b - a; } sort(ptr, ptr + 2*n); for (int i = 0; i < n; i++) { sum += ptr[i]; } cout << sum; return 0; } ///top1zata.blogspot.com

This comment is hidden due to too much negative feedback. Show it anyway.

41

tn165 commented on Sept. 26, 2022, 3:00 a.m. ← edited →

Ý tưởng thuật toán:

_ Ban đầu giả sử chọn toàn bộ 2n bài cho người 1 giải. Khi đó sum = tổng các ai

_ Sau đó kiểm tra xem n bài nào đưa người 2 giải thì tốt hơn.

_ Bài nào đưa người 2 giải thì sum += (bi - ai)

_ Dùng một vector lưu 2n giá trị (bi - ai)

_ Sau đó sort để lấy n bài mà chênh lệch (bi - ai) là nhiều nhất, lấy n bài đó cho người 2 giải

-17

ObitiDev commented on June 27, 2022, 4:02 a.m.

bạn nào cho mình hỏi thuật toán để giải bài này ạ.

This comment is hidden due to too much negative feedback. Show it anyway.

-83

thuanht commented on Nov. 4, 2021, 2:02 p.m.

include <bits/stdc++.h>

using namespace std;

int main() { iosbase::syncwith_stdio(false); cin.tie(NULL); int n; cin >> n; int sum = 0; int* ptr = new int[2n]; int i = 0; while(i < 2n) { int a,b; cin >> a >> b; sum += a; ptr[i++] = b - a; } sort(ptr, ptr + 2*n); for (int i = 0; i < n; i++) { sum += ptr[i]; } cout << sum; return 0; }

This comment is hidden due to too much negative feedback. Show it anyway.

ACM