Hướng dẫn giải của [Beginner Free Contest 11] AQUERY2
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Tổng số phần tử có thể lên tới ~10^{14}~ nên không ghi được cả dãy. Đề hỏi phần tử nhỏ thứ K: sắp các cặp (giá trị, số lần) rồi cộng dồn số lần.
Sub 1: Vét cạn - ~O(S \log S)~, dùng khi ~b_i \le 10~ (S là tổng số phần tử, ~S \le 10^6~)
Ghi thực sự cả dãy rồi sắp xếp và lấy phần tử thứ K. Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Sắp cặp và cộng dồn - ~O(Q \log Q)~
Sắp các cặp theo giá trị, cộng dồn số lần đến khi đạt ~K~ thì in giá trị hiện tại. Bẫy: tổng số lần lên tới ~10^{14}~ nên dùng long long. Đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu, nếu max ~b_i \le 10~ gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int Q;
long long K;
vector<long long> A, B; // thao tac i: them B[i] so co gia tri A[i] vao cuoi day
// Sub 1: vet can - ghi thuc day so ra mang roi sap xep. Dung khi moi b_i <= 10 (tong <= 10^6).
void sub1() {
vector<long long> v;
for (int i = 0; i < Q; i++)
for (long long t = 0; t < B[i]; t++) v.push_back(A[i]);
sort(v.begin(), v.end());
cout << v[K - 1] << "\n";
}
// Sub 2: sap xep cac cap (gia tri, so lan), cong don so lan cho den khi du K.
void sub2() {
vector<pair<long long, long long>> v;
for (int i = 0; i < Q; i++) v.push_back({A[i], B[i]});
sort(v.begin(), v.end());
long long acc = 0;
for (auto& pr : v) {
acc += pr.second;
if (acc >= K) {
cout << pr.first << "\n";
return;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> Q;
A.resize(Q);
B.resize(Q);
long long maxb = 0;
for (int i = 0; i < Q; i++) {
cin >> A[i] >> B[i];
maxb = max(maxb, B[i]);
}
cin >> K;
if (maxb <= 10) sub1();
else sub2();
return 0;
}
Bình luận