Hướng dẫn giải của [Free Contest 04] EXPLORE
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
Bessie phải thăm lần lượt tất cả thắng cảnh theo thứ tự khoảng cách |x| tăng dần, không được bỏ qua. Cô dừng khi hết thời gian, nên đáp án là độ dài tiền tố dài nhất của dãy đã sắp xếp mà quãng đường tích lũy không vượt quá T.
Mô phỏng trực tiếp — ~O(N\log N)~
Sắp xếp các thắng cảnh theo |x|. Đi từ 0 qua từng thắng cảnh theo thứ tự, cộng dồn quãng đường ~|x_k - x_{k-1}|~ và dừng ngay khi vượt quá T. Đáp án là số thắng cảnh đã đi qua.
Nếu chỉ nộp sub này: đúng 10/10 test. Đề không chia subtask nên chỉ viết 1 sub.
Chương trình hoàn chỉnh
Đây là lời giải đầy đủ, chỉ có một sub vì đề không chia subtask.
#include <bits/stdc++.h>
using namespace std;
long long T;
int N;
vector<long long> x; // vi tri cac thang canh
// Bessie phai tham quan TAT CA thang canh theo thu tu khoang cach |x| tang dan (khong duoc bo qua).
// Vay dap an la so thang canh lon nhat trong tien to cua day sap xep ma tong quang duong <= T.
// Chi co mot cach lam (mo phong tien to), khong co subtask nen viet 1 sub.
void sub1() {
vector<long long> p = x;
sort(p.begin(), p.end(), [](long long a, long long b) { return llabs(a) < llabs(b); });
long long cur = 0, cost = 0;
int ans = 0;
for (int i = 0; i < N; i++) {
cost += llabs(p[i] - cur); // di tu vi tri hien tai den thang canh tiep theo
cur = p[i];
if (cost > T) break;
ans++;
}
cout << ans << "\n";
}
int main() {
cin >> T >> N;
x.resize(N);
for (int i = 0; i < N; i++) cin >> x[i];
sub1();
return 0;
}
Bình luận