Hướng dẫn giải của Bedao Mini Contest 15 - SEQGAME2
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.
Tác giả:
Với mỗi vị trí i có ~ 1 \le a[i] \le N~ ta tính ~F[i]~ là số lần dịch chuyển cần thiết để đưa ~a[i]~ về đúng vị trí .
Ta có ~cnt[x]~ là số lượng vị trí ~i~ mà có ~F[i] = x~.
Nhận thấy rằng các thao tác biến đổi không ảnh hướng đến nhau. Giả sử ta thực hiện ~x~ lần dịch phải, thì số thao tác cần thiết để biến đổi dãy về dạng ~1 , 2 , ... , N~ là ~x + n - cnt[x]~.
Ta dùng set để lưu lại các giá trị ~ x - cnt[x]~ , tìm giá trị nhỏ nhất để bước biến đổi là min.
Code mẫu
/*#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma")*/ #include <bits/stdc++.h> #define for1(i,a,b) for (int i = a; i <= b; i++) #define for2(i,a,b) for (int i = a; i >= b; i--) #define int long long #define sz(a) (int)a.size() #define pii pair<int,int> #define pb push_back /* __builtin_popcountll(x) : Number of 1-bit __builtin_ctzll(x) : Number of trailing 0 */ const long double PI = 3.1415926535897932384626433832795; const int INF = 1000000000000000000; const int MOD = 1000000007; const int MOD2 = 1000000009; const long double EPS = 1e-6; using namespace std; const int N = 1e5 + 5; set<pii> se; int cnt[N], a[N], n, q; int dist(int a, int b) { if (b >= a) return b - a; return n - a + b; } void add(int i, int v) { int x = dist(i, v); se.erase({n + x - cnt[x], x}); cnt[x]++; se.insert({n + x - cnt[x], x}); } void del(int i, int v) { int x = dist(i, v); se.erase({n + x - cnt[x], x}); cnt[x]--; se.insert({n + x - cnt[x], x}); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("cf.inp", "r", stdin); // freopen("cf.out", "w", stdout); cin >> n; for1(i,0,n - 1) se.insert({n + i, i}); for1(i,1,n) { cin >> a[i]; if (a[i] <= n) add(i, a[i]); } cin >> q; while (q--) { int i, v; cin >> i >> v; if (a[i] <= n) del(i, a[i]); a[i] = v; if (a[i] <= n) add(i, a[i]); cout << (*se.begin()).first << "\n"; } }
Bình luận