Chọn bi

Xem dạng PDF
Gửi bài giải
Điểm: 0,01 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: chonbi.inp
Output: chonbi.out
Tác giả:
bedao
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bờm đi siêu thị, trong siêu thị có ~M~ loại màu bi khác nhau, loại bi màu ~i~ có ~a_i~ hộp, mỗi hộp có ~b_i~ viên bi. Giá mỗi hộp bi là như nhau. Bờm cần mua ~N~ hộp bi để tổng số bi trong ~N~ hộp là nhiều nhất.

Yêu cầu: Cho ~N~ là số hộp bi Bờm cần mua và ~M~ là số màu các hộp bi. Hãy lập trình giúp Bờm chọn ~N~ hộp bi sao cho tổng số bi mua được là nhiều nhất.

Input

Vào từ tệp văn bản CHONBI.INP:

  • Dòng đầu tiên hai số ~N, M~ ~(N, M \leq 10^4)~.

  • ~M~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~a_i~ và ~b_i~ ~(1 \leq a_i, b_i \leq 10^5)~.

  • Dữ liệu vào đảm bảo luôn đủ ~N~ hộp để Bờm mua.

Output

Ghi ra file CHONBI.OUT:

  • Một dòng gồm số lượng viên bi nhiều nhất trong ~N~ hộp Bờm mua được.

Sample Input 1

7 3
5 10
2 5
3 6

Sample Output 1

62

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 2
    23162035  đã bình luận lúc 9, Tháng 8, 2025, 13:59
    • Số lượng viên bi nhiều nhất trong n hộp Bờm mua được có nghĩa là ta sẽ mua trước những hộp có b[i] là lớn nhất. Do đó ý tưởng của mình như sau: Sắp xếp b[i] giảm dần, duyệt từ đầu, lấy càng nhiều hộp của loại hiện tại càng tốt(tối đa a[i], không quá số lượng hộp còn thiếu) rồi cộng với tak * b[i] cho ra kết quả cần tìm

  • -2
    baosonnguyenthe20  đã bình luận lúc 24, Tháng 6, 2025, 18:39

    code tk nhe y tuong la tham lam thui

    include <bits/stdc++.h>

    define fi first

    define se second

    define ll long long

    define N int(1e4)

    using namespace std; ll n, m, kq; pair<ll, ll>p[N + 10]; bool sx(pair<ll, ll> x, pair<ll, ll> y) { if (x.se == y.se) return x.fi > y.fi; return x.se > y.se; } int main() { ios::syncwithstdio(false); cin.tie(nullptr); freopen("chonbi.inp", "r", stdin); freopen("chonbi.out", "w", stdout); cin >> n >> m; for (int i = 1; i <= m; i++) cin >> p[i].fi >> p[i].se; sort(p + 1, p + m + 1, sx); for (int i = 1; i <= m; i++) { while (n > 0 && p[i].fi > 0) {

            kq += p[i].se;
        n--;
        p[i].fi--;
    }
    if (n == 0)
        {
            cout << kq;
            return 0;
        }
}
return 0;

    }


  • -3
    hoangquan2509  đã bình luận lúc 21, Tháng 5, 2025, 13:17

    ..


  • -8
    tranbaphu098  đã bình luận lúc 17, Tháng 4, 2025, 11:24

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -9
      kevinknguyen  đã bình luận lúc 20, Tháng 5, 2025, 7:33

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.