# 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;
}
cmducyd
Created at
25 likes
Phatgivp10
Created at
1 likes