fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll INF = (1LL<<62);
  5.  
  6. // Tính cost[t-1] = minimal total steps để đưa tất cả K học sinh (pos) vào các vị trí t..t+K-1
  7. // Xử lý bằng cách nhân đôi mảng pos và thử mọi rotation idx (chọn K học sinh liên tiếp bắt đầu từ idx)
  8. vector<ll> compute_costs_bruteforce(int N, int K, vector<int>& pos) {
  9.     if (K == 0) return vector<ll>(N, 0);
  10.     vector<int> P = pos;
  11.     sort(P.begin(), P.end());
  12.     vector<int> A(2*K);
  13.     for (int i = 0; i < K; ++i) {
  14.         A[i] = P[i];
  15.         A[i+K] = P[i] + N;
  16.     }
  17.     // D[k] = A[k] - k
  18.     vector<ll> D(2*K);
  19.     for (int k = 0; k < 2*K; ++k) D[k] = (ll)A[k] - (ll)k;
  20.     // prefix sums of D
  21.     vector<ll> pref(2*K+1, 0);
  22.     for (int i = 0; i < 2*K; ++i) pref[i+1] = pref[i] + D[i];
  23.  
  24.     vector<ll> cost(N, INF);
  25.     // với mỗi start t (1..N)
  26.     for (int t = 1; t <= N; ++t) {
  27.         // thử mọi rotation idx = 0..K (tức chọn K học sinh A[idx..idx+K-1])
  28.         // val = t - idx
  29.         for (int idx = 0; idx <= K; ++idx) {
  30.             int l = idx, r = idx + K; // đoạn trên D: [l, r)
  31.             // val
  32.             ll val = (ll)t - (ll)idx;
  33.             // tìm số phần tử trong D[l..r-1] <= val
  34.             int m = (int)(upper_bound(D.begin()+l, D.begin()+r, val) - (D.begin()+l));
  35.             ll sumLeft = val * (ll)m - (pref[l+m] - pref[l]);
  36.             ll sumRight = (pref[r] - pref[l+m]) - val * (ll)(K - m);
  37.             ll cur = sumLeft + sumRight;
  38.             if (cur < cost[t-1]) cost[t-1] = cur;
  39.         }
  40.     }
  41.     return cost;
  42. }
  43.  
  44. // Sparse table cho RMQ (min)
  45. struct SparseTable {
  46.     int n, LOG;
  47.     vector<vector<ll>> st;
  48.     vector<int> lg;
  49.     SparseTable() {}
  50.     SparseTable(const vector<ll>& a) {
  51.         n = (int)a.size();
  52.         lg.assign(n+1, 0);
  53.         for (int i=2;i<=n;++i) lg[i] = lg[i>>1] + 1;
  54.         LOG = lg[n];
  55.         st.assign(LOG+1, vector<ll>(n));
  56.         st[0] = a;
  57.         for (int k = 1; k <= LOG; ++k) {
  58.             for (int i = 0; i + (1<<k) <= n; ++i) {
  59.                 st[k][i] = min(st[k-1][i], st[k-1][i + (1<<(k-1))]);
  60.             }
  61.         }
  62.     }
  63.     ll range_min(int l, int r) { // inclusive
  64.         if (l > r) return INF;
  65.         int len = r - l + 1;
  66.         int k = lg[len];
  67.         return min(st[k][l], st[k][r - (1<<k) + 1]);
  68.     }
  69. };
  70.  
  71. int main() {
  72.     ios::sync_with_stdio(false);
  73.     cin.tie(nullptr);
  74.     int T;
  75.     if (!(cin >> T)) return 0;
  76.     while (T--) {
  77.         int N, M, L;
  78.         cin >> N >> M >> L;
  79.         vector<int> P(M), Q(L);
  80.         for (int i = 0; i < M; ++i) cin >> P[i];
  81.         for (int i = 0; i < L; ++i) cin >> Q[i];
  82.         sort(P.begin(), P.end());
  83.         sort(Q.begin(), Q.end());
  84.  
  85.         // dùng phiên bản sửa: đúng nhưng có thể chậm với dữ liệu cực lớn
  86.         vector<ll> costP = compute_costs_bruteforce(N, M, P);
  87.         vector<ll> costQ = compute_costs_bruteforce(N, L, Q);
  88.  
  89.         // duplicate costQ để xử lý đoạn trên vòng tròn
  90.         vector<ll> costQ2(2*N);
  91.         for (int i = 0; i < 2*N; ++i) costQ2[i] = costQ[i % N];
  92.  
  93.         SparseTable st(costQ2);
  94.  
  95.         ll ans = INF;
  96.         for (int t1 = 1; t1 <= N; ++t1) {
  97.             int l = t1 + M;
  98.             int r = t1 + N - L;
  99.             int Lidx = l - 1;
  100.             int Ridx = r - 1;
  101.             if (Lidx < 0) Lidx = 0;
  102.             if (Ridx >= 2*N) Ridx = 2*N - 1;
  103.             if (Lidx <= Ridx) {
  104.                 ll bestQ = st.range_min(Lidx, Ridx);
  105.                 ans = min(ans, costP[t1-1] + bestQ);
  106.             }
  107.         }
  108.         cout << ans << "\n";
  109.     }
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
1
12 6 4
1 3 5 7 9 11
2 12 8 4
stdout
copy 
15
https://ideone.com/QnlKCf
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!