# Nhắc nhở
## Khuyến khích mọi người nên tự tìm hiểu, suy nghĩ lời giải trước khi tham khảo
## Nên đọc kỹ hướng dẫn trước khi tham khảo bài làm
_____________________________________________________________________________________________________________
### Cách 1: Bỏ ra từng cân nặng của từng viên kẹo vào một mảng rồi sắp xếp lấy kết quả
Đầu tiên, ta sử dụng cấu trúc struct(hoặc dùng pair) để nhập vào số lượng viên kẹo và cân nặng của chúng.
```
bool cmp(keo a,keo b)
{
return a.g<b.g;
}
```
Tiếp theo ta sẽ sử dụng hàm so sánh hai struct và sort lại mảng theo hàm so sánh. Rồi sau đó in ra cân nặng viên kẹo thứ k.
Bạn có thể tham khảo code như sau.
```
#include <bits/stdc++.h>
#define ll long long
const int N=1e6;
using namespace std;
int n,q;
ll k;
struct keo
{
int sl,g;
};
keo a[N+10];
bool cmp(keo a,keo b)
{
return a.g<b.g;
}
vector<int>v;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> q;
for(int i=0;i<n;i++)
{
cin >> a[i].sl >> a[i].g;
}
sort(a,a+n,cmp);
for(int i=0;i<n;i++)
{
while(a[i].sl--)
{
v.push_back(a[i].g);
}
}
while(q--)
{
cin >> k;
cout << v[k-1] << '\n';
}
return 0;
}
```
**-Lưu ý: Cách này có thể bị tràn bộ nhớ do k <= 1e14**
### Cách 2: Sử dụng tìm kiếm nhị phân
> Độ phức tạp: ***O(n*log(n))***
> Ngôn ngữ: ***C++14***
Chúng ta sử dụng pair để nhập số lượng và cân nặng của từng loại kẹo, đồng thời lập mảng a[i] để lưu các giá trị f[i],
với f[i] là tổng tiền tố của mảng p[i].first(lưu các số lượng của từng loại kẹo) . Sau đó sử dụng lập hàm so sánh và sort lại mảng pair.
Tiếp theo, ta sẽ lập hàm tìm kiếm nhị phân để tìm vị trí đầu tiên của phần tử >=k trong mảng a[i].
Bạn có thể tham khảo code như sau:
```
#include <bits/stdc++.h>
#define ll long long
const int N=1e5;
using namespace std;
int n,q,d;
ll a[N+10];
pair<int,int>p[N+10];
bool cmp(pair<int,int>a,pair<int,int>b)
{
return a.second<b.second;
}
ll f[N+10];
int trai(ll a[],int l,int r,ll x)//Bạn có thể sử dụng lower_bound để thay thế
{
int res=-1;
while(l<=r)
{
int m=(l+r)/2;
if(a[m]>=x)
{
r=m-1;
res=m;
}else l=m+1;
}
return res;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(NULL);
cin >> n >> q;
for(int i=0;i<n;i++)
{
cin >> p[i].first >> p[i].second;
}
sort(p,p+n,cmp);
for(int i=0;i<n;i++)
{
f[i]=f[i-1]+p[i].first;
a[i]=f[i];
}
while(q--)
{
ll k;
cin >> k;
int dau=trai(a,0,n-1,k);
if(dau!=-1)
{
cout << p[dau].second << '\n';
}
}
return 0;
}
```
# Problem Analysis and Solution
## Problem Statement
Có N loại viên kẹo trên bàn, mỗi loại kẹo có 2 số:
- `a[i]` là số viên kẹo loại i.
- `w[i]` là cân nặng mỗi viên kẹo.
Biết rằng tất cả viên kẹo sẽ được đổ lên bàn và sắp xếp theo thứ tự không giảm (dãy tăng). Cho `q` truy vấn, với mỗi truy vấn `q[i]`, hỏi viên kẹo thứ `q[i]` nặng bao nhiêu?
---
## Problem Analysis
- Dãy con không giảm được cho, do đó có thể sử dụng **binary search**.
- Xác định số viên kẹo tối đa của từng loại.
- Xây dựng mảng chứa số lượng tối đa nếu xếp tất cả viên kẹo ra.
Ví dụ:
- Input mẫu:
3 3
2 2
1 1
3 3
1
3
5
- Sau khi sắp xếp, ta có:
1 1
2 2
3 3
- Dãy tối đa (gọi là `pos[i]`):
- 1-->3-->6
- Dựa vào khoảng `pos[i]` và `pos[i+1]`, dùng **binary search** để xác định vị trí của `q[i]`.
---
## Implementation
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
signed main() {
fast;
int n, q;
cin >> n >> q;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++) cin >> a[i].second >> a[i].first;
vector<int> query(q);
for (int i = 0; i < q; i++) {
cin >> query[i];
}
sort(a.begin(), a.end()); // Sort the candies
vector<int> pos(n);
pos[0] = a[0].second;
for (int i = 1; i < n; i++) {
pos[i] = pos[i - 1] + a[i].second; // Create the `pos` array
}
// Perform binary search to find the appropriate range
for (int i = 0; i < q; i++) {
int l = 0, r = n - 1, submid = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (pos[mid] < query[i]) {
l = mid + 1;
} else {
submid = mid;
r = mid - 1;
}
}
if (submid != -1) {
cout << a[submid].first << endl;
}
}
return 0;
}
## Cảm ơn ADMIN nhé! Chỉ đọc gợi ý để có hướng giải không nên sao chép hoàn toàn
## Nhận xét quan trọng
Tổng số viên kẹo có thể rất lớn (tối đa $10^{14}$) — không thể dựng hoặc duyệt toàn bộ dãy từng viên. Vì vậy ta xử lý theo đoạn cho mỗi loại kẹo: mỗi loại chiếm một đoạn liên tiếp trong dãy sau khi sắp xếp theo khối lượng.
## Ý tưởng
Gom dữ liệu thành cặp $(w_i, a_i)$.
Sắp xếp các cặp theo $w_i$ tăng dần.
Xây mảng tổng cộng dồn số lượng viên kẹo tại mỗi giá trị i
Với mỗi truy vấn **`k`**, ta chỉ cần tìm chỉ số nhỏ nhất **`j`** sao cho:
👉 **`pref[j] ≥ k`**
Khi đó:
- Viên kẹo thứ **`k`** chắc chắn thuộc loại **`j`**.
- Đáp án chính là a [ j ].
## Độ phức tạp
Sắp xếp: $O(n\log n)$.
Xây pref: $O(n)$.
Mỗi truy vấn: $O(\log n)$.
Tổng: $O(n\log n + q\log n)$ — phù hợp với ràng buộc.
## Code mẫu
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, q;
cin >> n >> q;
vector<pair<ll, ll>> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i].f >> a[i].s; // ai, wi
}
// sắp xếp theo khối lượng w tăng dần
sort(a.begin(), a.end(), [](auto &x, auto &y) {
return x.s < y.s;
});
// mảng prefix của số kẹo
vector<ll> pref(n + 1, 0);
for (int i = 1; i <= n; i++) {
pref[i] = pref[i - 1] + a[i - 1].f;
}
while (q--) {
ll k;
cin >> k;
ll it = lower_bound(pref.begin(), pref.end(), k) - pref.begin(); // tìm kiếm vị trí >= k
cout << a[it - 1].s << "\n"; // trừ 1 vì chỉ số mảng pref hơn mảng a 1 đơn vị
}
}
```
cmducyd
Created at
28 likes
Phatgivp10
Created at
3 likes
betapcode24
Created at
1 likes