HSG9 Cà Mau 2026 - Tặng quà

Xem dạng PDF

Gửi bài giải

Điểm: 14,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Ban tổ chức hội trại có chuẩn bị các món quà lưu niệm dành tặng cho các trại sinh trong đợt tham gia hội trại. Có ~N~ món quà, với món quà thứ ~i~ sẽ có cân nặng ~P_i~ (với mỗi món quà ở vị trí ~i~, ban tổ chức có thể phát cho nhiều trại sinh nhưng một trại sinh không thể nhận nhiều hơn hoặc bằng ~2~ lần cùng một món quà ở vị trí ~i~).

Trong hội trại, có ~Q~ trại sinh và mỗi trại sinh có thể mang theo ~X~ cân nặng. Ban tổ chức cần hướng dẫn các bạn trại sinh một lựa chọn sao cho nhận được nhiều món quà nhất có thể.

Yêu cầu: Có ~Q~ trại sinh, với trại sinh thứ ~j~ có thể mang theo ~X_j~ cân nặng. Hãy giúp ban tổ chức tính số lượng quà tối đa mà trại sinh có thể nhận được.

Input

  • Dòng ~1~: Hai số nguyên dương ~N~ và ~Q~ (~0 \le N, Q \le 10^5~);

  • Dòng ~2~: ~N~ số nguyên dương ~P_i~ (~1 \le P_i \le 10^4~);

  • ~Q~ dòng tiếp theo: mỗi dòng một số ~X_j~ (~1 \le X_j \le 10^9~).

Output

~Q~ dòng, mỗi dòng là số quà tối đa nhận được.

Scoring

Subtask Điểm Ràng buộc
1 ~40\%~ ~0 \le N, Q \le 10^3~, ~1 \le P_i \le 10^2~, ~1 \le X_j \le 10^3~;
2 ~40\%~ ~10^3 \le N, Q \le 10^5~, ~10^2 \le P_i \le 10^4~, ~10^3 \le X_j \le 10^5~;
3 ~20\%~ Không có giới hạn gì thêm

Sample Input 1

5 3
5 2 4 1 3
6
1
14

Sample Output 1

3
1
4

Notes

Có ~3~ trại sinh với phương án tối ưu được chọn như sau:

  • Với cân nặng ~X = 6~: Nhận được số quà tối đa ~3~ (~2 + 1 + 3 = 6~).

  • Với cân nặng ~X = 1~: Nhận được số quà tối đa ~1~ (~1 = 1~).

  • Với cân nặng ~X = 14~: Nhận được số quà tối đa ~4~ (~2 + 4 + 1 + 3 = 10~).


Bình luận

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



  • -1
    kelvin2206  đã bình luận lúc 14, Tháng 11, 2026, 13:33

    include <bits/stdc++.h>

    using namespace std;
    
    const int mxn=1e5+5;
    int n, q, a[mxn], x;
    long long pf[mxn];
    
    bool p(long long a, int k) {
        return a<=k;
    }
    
    int bs(long long a[], int k) {
        int l=0, r=n, m, ans=0;
        long long sum;
        while(l<=r) {
            m=l+(r-l)/2;
            sum=a[m]-a[0];
            if(p(sum, k)) {
                ans=m;
                l=m+1;
            }
            else {
                r=m-1;
            }
        }
        return ans;
    }
    
    void solve() {
        cin >> n >> q;
        for(int i=0; i&lt;n; ++i) {
            cin >> a[i];
        }
        sort(a, a+n);
        for(int i=1; i<=n; ++i) {
            pf[i]=pf[i-1]+a[i-1];
        }
        while(q--) {
            cin >> x;
            cout << bs(pf, x) << '\n';
        }
    }
    
    int main() {
        ios::sync_with_stdio(0);
        cin.tie(nullptr);
    
            solve();
    
        return 0;
    }
    

  • -1
    thinhphamminh274  đã bình luận lúc 10, Tháng 11, 2026, 5:23

    PHÂN TÍCH BÀI TOÁN VÀ GIẢI THUẬT: TẶNG QUÀ

    1. Phân tích bài toán

    • Đề bài:
      • Có $N$ món quà với trọng lượng lần lượt là $P1, P2, \dots, P_N$[cite: 2].
      • Có $Q$ truy vấn (tương ứng với $Q$ trại sinh), mỗi trại sinh có sức chứa trọng lượng tối đa là $X$[cite: 2].
      • Cần tìm số lượng quà tối đa mà một trại sinh có thể mang đi sao cho tổng trọng lượng của các món quà đó không vượt quá sức chứa $X$ của họ[cite: 2].
    • Ý tưởng tham lam (Greedy):
      • Để lấy được số lượng quà nhiều nhất, ta nên ưu tiên chọn những món quà có trọng lượng từ nhỏ đến lớn.
      • Do đó, ta cần sắp xếp lại danh sách các món quà theo thứ tự tăng dần về cân nặng.

    2. Giải thuật chi tiết

    Bước 1: Đọc dữ liệu và sắp xếp
    • Đọc vào số lượng món quà $N$ và số lượng truy vấn $Q$[cite: 2].
    • Đọc trọng lượng của $N$ món quà vào mảng $a$[cite: 2].
    • Sắp xếp mảng $a$ theo thứ tự tăng dần từ phần tử $1$ đến $N$ (sort(a + 1, a + n + 1)):
      • Giúp các món quà nhẹ hơn đứng trước, thuận lợi cho việc chọn nhiều quà nhất có thể.
    Bước 2: Xây dựng mảng cộng dồn (Prefix Sum)
    • Tạo mảng pre với pre[i] lưu tổng trọng lượng của $i$ món quà nhẹ nhất sau khi đã sắp xếp: $$\text{pre}[i] = \text{pre}[i-1] + a[i]$$
    • Mảng pre có tính chất tăng dần, giúp ta nhanh chóng biết được tổng trọng lượng khi lấy $i$ món quà nhẹ nhất.
    Bước 3: Xử lý các truy vấn với Tìm kiếm nhị phân (Binary Search)
    • Với mỗi truy vấn có trọng lượng tối đa $X$ mà trại sinh có thể mang theo:
      • Ta cần tìm số lượng quà lớn nhất $it$ sao cho tổng trọng lượng của $it$ món quà đầu tiên không vượt quá $X$ ($\text{pre}[it] \le X$).
      • Sử dụng hàm upper_bound(pre + 1, pre + n + 1, x) để tìm vị trí đầu tiên có tổng trọng lượng lớn hơn $X$.
      • Trừ đi con trỏ đầu pre và trừ tiếp đi $1$ (- pre - 1), ta thu được số lượng món quà tối đa có thể chọn (it).
    • In kết quả ra màn hình cho mỗi truy vấn.

    3. Đánh giá độ phức tạp

    • Độ phức tạp sắp xếp: $O(N \log N)$ để sắp xếp mảng quà.
    • Độ phức tạp truy vấn: Mỗi truy vấn sử dụng upper_bound mất $O(\log N)$. Với $Q$ truy vấn, tổng thời gian xử lý truy vấn là $O(Q \log N)$.
    • Tổng độ phức tạp thời gian: $O((N + Q) \log N)$, hoàn toàn chạy mượt mà với giới hạn $N, Q \le 10^5$.
      #include <bits/stdc++.h>
      #define ll long long
      #define Sonic() cin.tie(NULL)->syncwithstdio(0);
      #define el '\n'
      using namespace std;
      ll a[100005];
      ll pre[100005];
      int main(){
          Sonic();
          ll n,q;cin>>n>>q;
          for(ll i=1;i<=n;i++)cin>>a[i];
          sort(a+1,a+n+1);
          for(ll i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
          while(q--){
              ll x;cin>>x;
              ll it=upper_bound(pre+1,pre+n+1,x)-pre-1;
              cout<<it<<el;
          }
          return 0;
      }