``` cpp
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
// Ham so sanh ti le gia tri tren khoi luong giam dan
bool getSosanhtile(const pair<int, int>& a, const pair<int, int>& b)
{
return (double)a.first / a.second > (double)b.first / b.second;
}
// Ham rut gon phan so
pair<int, int> getRutgonphanso(int tuso, int mauso)
{
int gcd = __gcd(tuso, mauso);
return {tuso / gcd, mauso / gcd};
}
int main()
{
ifstream fin("DIAMOND.inp");
int N, K;
fin >> N >> K;
vector<int> vGiatri(N); // Mang luu gia tri cua cac vien kim cuong
vector<int> vKhoiluong(N); // Mang luu khoi luong cua cac vien kim cuong
for (int i = 0; i < N; ++i)
{
fin >> vGiatri[i] >> vKhoiluong[i];
}
fin.close();
// Tao mot vector cac cap gia tri, khoi luong
vector<pair<int, int>> capgiatrikhoiluong;
for (int i = 0; i < N; ++i)
{
capgiatrikhoiluong.push_back({vGiatri[i], vKhoiluong[i]});
}
// Sap xep cac vien kim cuong theo ti le gia tri tren khoi luong giam dan
sort(capgiatrikhoiluong.begin(), capgiatrikhoiluong.end(), getSosanhtile);
// Chon ra K vien kim cuong co ti le gia tri tren khoi luong lon nhat
int tonggiatri = 0;
int tongkhoiluong = 0;
for (int i = 0; i < K; ++i)
{
tonggiatri += capgiatrikhoiluong[i].first;
tongkhoiluong += capgiatrikhoiluong[i].second;
}
// Rut gon phan so cua tong gia tri tren tong khoi luong
pair<int, int> getRutgon = getRutgonphanso(tonggiatri, tongkhoiluong);
// Ghi ket qua vao file output
ofstream fout("DIAMOND.out");
fout << getRutgon.first << " " << getRutgon.second << endl;
fout.close();
return 0;
}
Đề bàiTác giả: Vàng Văn Quyn
Những tin mới hơn
Những tin cũ hơn
- Click vào nút hiển thị ngày trong tuần hoặc tháng âm lịch để xem chi tiết
- Màu đỏ: Ngày tốt
- Xanh lá: Đầu tháng âm lịch
- Màu vàng: Ngày hiện tại