Thưởng
Xem dạng PDF
Mã bài:
thuong
Điểm:
2 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python, Scratch
Để kết thúc buổi sinh hoạt lớp lập trình, thầy giáo bộ môn đã chuẩn bị N (1≤N≤500000, N chẵn) phần quà cho hai tổ. Mỗi tổ gán một giá trị ưu thích (là một số nguyên dương ≤100) mà mình nghĩ vào phần quà. Sau đó, thầy giáo cho mỗi tổ nhận N/2 phần quà sao cho tổng giá trị ưu thích của hai tổ lớn nhất.
Yêu cầu: Bạn hãy giúp thầy giáo tìm tổng giá trị ưa thích lớn nhất của hai tổ theo cách chia quà trên.
Dữ liệu: vào từ file THUONG.INP có cấu trúc:
- Dòng 1 chứa số nguyên dương chẵn N
- N dòng tiếp theo, mỗi dòng chứa hai số nguyên ai và bi là giá trị tổ 1 và 2 gán cho món quà thứ i.
Kết quả: ghi file THUONG.OUT một số nguyên duy nhất là tổng số giá trị ưa thích lớn nhất sau khi mỗi tổ đã chọn N/2 phần quà.
Ví dụ
| input | output | Giải thích |
|---|---|---|
| 4 1 2 2 3 3 5 2 1 |
11 | Tổ 1 chon quà thứ 1 và 4, tổ 2 chọn quà thứ 2 và 3 |
Bình luận
include<bits/stdc++.h>
using namespace std; long long d[500005]; int main() { iosbase::syncwith_stdio(0); cin.tie(0);cout.tie(0); long long n; cin>>n; long long ans=0; for(int i=0;i<n;i++) { long long a,b; cin>>a>>b; ans+=b; d[i]=a-b; } sort(d,d+n,greater<long long>()); for(long long i=0;i<n/2;i++) { ans+=d[i]; } cout<<ans; return 0; }