# 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;
}
```
cmducyd
Created at
23 likes