Nội dung Bài tập
- Mã:
- GROUP
- Tên:
- GROUP - Phân nhóm
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- admin
Cho n<=300000 cặp số (x,y) (1<=x, y<=1000000). Ta có thể nhóm một vài cặp số lại thành một nhóm. Giả sử một nhóm gồm các cặp số thứ a1, a2, ..., am thì chi phí cho nhóm này sẽ là max(xa1, xa2, ..., xam) * max(ya1, ya2, ..., yam).
Yêu cầu: tìm cách phân nhóm có tổng chi phí bé nhất.
Dữ liệu
- Dòng đầu tiên là số nguyên dương N.
- N dòng tiếp theo dòng thứ i ghi 2 số xi và yi.
Kết quả
- Gồm 1 số duy nhất là kết quả tìm được.
Ví dụ
Input Output
Nguồn: http://vn.spoj.com/problems/GROUP/Giải thích: Có 3 nhóm lần lượt là (1), (2,3) và (4).
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...