Hướng dẫn giải của VÒNG TRÒN (CỤM BN4)
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
Có N yêu cầu xếp vòng tròn. Nếu bắt đầu từ yêu cầu s, yêu cầu thứ k được bắt đầu lúc k \cdot \Delta (k từ 1), và thời điểm hoàn thành cuối cùng là max của (kj \cdot \Delta + aj). Cần chọn s để giá trị này nhỏ nhất. Các a_i tính theo công thức đề bài, dùng long long vì p \cdot i có thể lớn.
Sub 1: Thử mọi điểm bắt đầu — ~O(N^2)~, dùng khi ~N \le 1000~
Với mỗi s, duyệt mọi j để tính thời điểm hoàn thành lớn nhất, rồi lấy min theo s. Nếu chỉ nộp sub này: đúng 4/8 test.
Sub 2: Cửa sổ trượt — ~O(N)~
Nối đôi dãy, đặt ct = a{t mod N} + t \cdot \Delta. Với điểm bắt đầu s, thời điểm hoàn thành bằng max của c_t trên đoạn [s, s + N - 1], trừ s \cdot \Delta rồi cộng \Delta. Dùng deque để lấy max của mọi cửa sổ có độ dài N. Sub 2 đúng 8/8 test.
Chương trình hoàn chỉnh
Hàm main đọc N, \Delta, p, q, m, tính a_i. Nếu N \le 1000 gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
long long N, Delta, p, q, m;
vector<long long> a; // a[i] = (p*i) % m + q, i = 1..N (lưu ở a[i-1])
// Với yêu cầu bắt đầu xử lý tại vị trí s (0-based), yêu cầu thứ j (0-based) được bắt đầu
// lúc (k + 1) * Delta, với k = (j - s) mod N. Thời điểm hoàn thành cuối cùng:
// max_j ( (k_j + 1) * Delta + a_j )
// Lấy min theo s.
// Sub 1: thử mọi s, mỗi s tính max trong O(N): O(N^2). Dùng khi N <= 1000.
void sub1() {
long long best = LLONG_MAX;
for (long long s = 0; s < N; s++) {
long long worst = 0;
for (long long j = 0; j < N; j++) {
long long k = (j - s + N) % N;
worst = max(worst, (k + 1) * Delta + a[j]);
}
best = min(best, worst);
}
cout << best << "\n";
}
// Sub 2: O(N). Viết lại trên mảng nối đôi: c_t = a[t mod N] + t * Delta với t = 0..2N-2.
// Với s, thời điểm hoàn thành = max_{t in [s, s+N-1]} c_t - s * Delta + Delta.
// Dùng cửa sổ trượt (deque) để lấy max trên các cửa sổ có độ dài N.
void sub2() {
deque<long long> dq; // lưu chỉ số t, giá trị c_t giảm dần
auto c = [&](long long t) { return a[t % N] + t * Delta; };
long long best = LLONG_MAX;
for (long long t = 0; t <= 2 * N - 2; t++) {
long long val = c(t);
while (!dq.empty() && c(dq.back()) <= val) dq.pop_back();
dq.push_back(t);
if (dq.front() < t - N + 1) dq.pop_front();
if (t >= N - 1) {
long long s = t - N + 1;
long long worst = c(dq.front()) - s * Delta + Delta;
best = min(best, worst);
}
}
cout << best << "\n";
}
int main() {
freopen("VONGTRON.INP", "r", stdin);
freopen("VONGTRON.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> Delta;
cin >> p >> q >> m;
a.resize(N);
for (long long i = 1; i <= N; i++) a[i - 1] = (p * i) % m + q;
if (N <= 1000) sub1();
else sub2();
return 0;
}
Bình luận