CANDY BOXES
Xem PDF
Điểm:
250 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bạn Lan có vô tận những viên kẹo. Các viên kẹo được đánh số \(1,2,...\).
Sau đó, Lan lần lượt bỏ các viên kẹo vào \(n\) hộp kẹo, sao cho hộp thứ \(i\) chứa được \(a_i\) viên kẹo.
Yêu cầu: Có \(Q\) truy vấn, mỗi truy vấn sẽ đặt ra một số nguyên \(k\) là thứ tự của \(1\) viên kẹo. Hãy cho biết viên kẹo thứ \(k\) này đang nằm trong hộp nào?
Input
- Dòng đầu ghi \(n\) không quá \(10^5\).
- Dòng thứ hai ghi \(n\) số nguyên dương \(a_1,a_2,...,a_n\) được sắp xếp tăng dần.
- Dòng thứ ba ghi số nguyên dương \(Q\) không quá \(10^5\).
- \(Q\) dòng tiếp theo, mỗi dòng ghi số nguyên \(k\) không quá \((1+2...+n)\)
Output
- Ứng với truy vấn thứ \(x\), in ra thứ tự của hộp kẹo đang chứa viên kẹo thứ \(x\).
Example
Test 1
Input
3
1 2 3
2
1
5Output
1
3
Bình luận
Spoiler AlertHình ảnh minh họa thuật toán:
Hint 1: < Cày trâu >
if(k > a[i]) k -= a[i];
else {
cout << i << endl;
break;
}
Full Code| O(N * Q) | 70% - 80% Test | TLE
#include<bits/stdc++.h>
using namespace std;
long long a[1000000];
int main ()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
long long n, q, k;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
cin >> q;
while(q --)
{
cin >> k;
for(int i = 1; i <= n; i ++)
{
if (k > a[i]) k -= a[i];
else
{
cout << i << endl;
break;
}
}
}
}
Hint 2: < Chặt nhị phân >
- Tương tự việc bỏ kẹo vào các hộp kẹo như cày trâu.
- Tạo một mảng tổng lưu giá trị tổng số viên kẹo từ hộp kẹo thứ 1 -> i.
- Chặt nhị phân mảng tổng để tìm vị trí.
Nếu các bạn chưa biết thuật toán chặt nhị phân, các bạn có thể tham khảo: Tại đây.
Minh họa giữa chặt nhị phân và cày trâu:
Full code| O (Q * (log(2, N) | 100% Test | AC
#include<bits/stdc++.h>
using namespace std;
long long a[1000000];
long long s[1000000];
int main ()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
long long n, q, k;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i], s[i] = s[i - 1] + a[i];
cin >> q;
while(q --)
{
cin >> k;
long long l = 1, r = n;
while (l <= r)
{
long long g = (l + r) / 2;
if (k <= s[g]) r = g - 1;
else l = g + 1;
}
cout << l << endl;
}
}
Nếu các bạn có thắc mắc gì thì có thể ib riêng cho mình: Tại đây