## KHUYÊN CÁC BẠN NÊN SUY NGHĨ TRƯỚC KHI ĐỌC SOLUTION NHAAA
## Ý tưởng
- Với mỗi xe i, ta bắt đầu từ p[i], nếu ô đó đã có người ta xét tiếp đến (p[i] + 1) % n, (p[i] + 2) % n, ...
đến khi tìm được ô trống.
Có thể thấy duyệt trâu như thế sẽ tốn **O(n)** cho mỗi xe dẫn đến độ phức tạp tổng lên đến **O(n \* n)**
dẫn đến **TLE**
- Ta có thể "nhảy" thẳng đến ô trống tiếp theo mà không cần duyệt trâu bằng cách dùng cấu trúc dữ liệu
**DSU**. Ta coi mỗi ô là một node trong **DSU**, và parent của mỗi node sẽ trỏ đến ô trống tiếp theo. Sau khi
ô **k** đã bị chiếm thì ta gộp **k** với **k + 1**.
## Hướng giải
- Gọi parent[i] là ô trống tiếp theo nếu muốn đậu ở điểm i.
- Ban đầu parent[i] = i, mọi ô đều trống nên i trỏ tới i
- Khi có xe muốn đậu tại k, ta tìm ô bằng cách gọi get_parent(k)
- Sau khi ô đó bị chiếm ta gộp parent[k] và parent[k + 1]
- Lặp lại cho mỗi xe
## CODE
### `[ARE YOU SURE YOU WANT TO PROCEED]`
```
/*
"I'm not sure I should even call it parent..."
- KevinPhan 19/06/2025 -
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
bool taken[100009];
int parent[100009], sz[100009];
int get_parent(int u)
{
if (u == parent[u]) return parent[u];
return parent[u] = get_parent(parent[u]);
}
bool join(int u, int v)
{
u = get_parent(u);
v = get_parent(v);
if (sz[u] < sz[v]) swap(u, v);
if (u == v) return false;
sz[u] += sz[v];
parent[v] = u;
return true;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) parent[i] = i, sz[i] = 1;
for (int i = 1; i <= n; i++)
{
int k;
cin >> k;
k = get_parent(k);
cout << k << ' ';
parent[k] = parent[k % n + 1];
}
return 0;
}
```
Ý tưởng không sử dụng DSU (Chặt nhị phân kết hợp Segment Tree)
Độ phức tạp: $O(n \cdot \log^2 n)$
Từ cách tiếp cận ban đầu, thuật toán có thể được cải tiến bằng cách khai thác một số nhận xét và sử dụng cấu trúc dữ liệu segment tree nhằm tối ưu quá trình tìm kiếm.
Thay vì phải lặp qua toàn bộ mảng để xác định các vị trí còn trống, ta mô hình hóa trạng thái của mảng bằng các giá trị nhị phân:
$0$: vị trí chưa bị chiếm,
$1$: vị trí đã bị chiếm.
Khi duyệt chỉ số $i$ từ $1$ đến $n$, mục tiêu là tìm chỉ số nhỏ nhất $j$ sao cho $a[j] = 0$, tức là vị trí chưa bị chiếm gần nhất theo thứ tự ưu tiên.
Ta có nhận xét quan trọng sau: một đoạn $[l, r]$ chứa ít nhất một phần tử bằng $0$ khi và chỉ khi tổng các phần tử trong đoạn nhỏ hơn độ dài của đoạn, tức là:
$pref[r]−pref[l−1]<r−l+1.$
Dựa trên nhận xét này, thuật toán được thực hiện như sau: với mỗi chỉ số $i$, tiến hành chặt nhị phân để tìm chỉ số nhỏ nhất $j$ trong đoạn $[i, n]$ sao cho đoạn đó vẫn còn tồn tại phần tử $0$. Nếu không tìm được, tiếp tục tìm trong đoạn $[1, i-1]$. Việc kiểm tra một đoạn có chứa phần tử $0$ hay không được thực hiện thông qua truy vấn tổng trên segment tree, trong đó luôn ưu tiên kiểm tra nửa bên trái trước để đảm bảo tìm được chỉ số nhỏ nhất thỏa mãn yêu cầu.
Sau khi xác định được vị trí $j$, ta cập nhật $a[j] = 1$ nhằm đánh dấu vị trí này đã bị chiếm.
Mặc dù code chạy hơi lâu và cài hơi cực xíu nhưng đây cũng là một cách để tham khảo thêm ^^
CODE MẪU:
```
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxN=1e5;
int seg[4*maxN+5];
int n;
void update(int id,int l,int r,int pos)
{
if(l==r)
{
seg[id]=1;
return;
}
int mid=(l+r)/2;
if(pos<=mid) update(id*2,l,mid,pos);
else update(id*2+1,mid+1,r,pos);
seg[id]=seg[id*2]+seg[id*2+1];
}
int get(int id,int l,int r,int u,int v)
{
if(l>v||r<u) return 0;
if(u<=l&&r<=v) return seg[id];
int mid=(l+r)/2;
return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v);
}
int bin(int start,int fin)
{
int l=start,r=fin;
int pos=-1;
while(l<=r)
{
bool check1=false;
int mid=(l+r)/2;
if(l==r)
{
if(get(1,1,n,l,mid)==0) pos=mid;
break;
}
int temp1=get(1,1,n,l,mid);
if(temp1<mid-l+1)
{
r=mid;
check1=true;
}
else
{
int temp2=get(1,1,n,mid+1,r);
if(temp2<r-mid)
{
l=mid+1;
check1=true;
}
}
if(!check1) break;
}
return pos;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;++i)
{
int x;
cin>>x;
int ans1=bin(x,n);
if(ans1==-1) ans1=bin(1,i-1);
update(1,1,n,ans1);
cout<<ans1<<" ";
}
//cout<<bin(2,n);
}
```
Lại là một cách nữa không sử dụng DSU nhưng dễ cài hơn
# Ý tưởng :
+ dùng set, với mỗi truy vấn x ta tìm phần tử nhỏ nhất >= x bằng lower_bound :
+ Nếu tìm thấy : xóa nó ra khỏi set
+ Nếu không tìm thấy : lấy phần tử đầu tiên trong set, xóa nó ra khỏi set
# Tại sao lại đúng?
+ Giả sử bãi đỗ xe k phải 1 vòng tròn mà là 1 dãy từ 1 -> n, với mỗi truy vấn ta cần tìm vị trí mới lớn hơn x, chưa bị chiếm, và vị trí đó cần nhỏ nhất có thể, nếu x chưa bị chiếm thì ta chiếm x.
+ Nếu giả định là như vậy thì ta có thể dùng 1 con trỏ và duyệt từ x đến n là được
+ Nhưng nó lại quá tốn thời gian,ta nhận thấy bãi đỗ xe đã đc sắp xếp từ 1 -> n, khi đó ta có thể dùng chặt nhị phân để tìm phần tử bé nhất >= x và chưa bị chiếm
+ Lúc này lại có vấn đề mới, làm sao để chặt nhị phân ko cho kết quả là 1 ô bị chiếm, lúc này nếu ta dùng set, mỗi truy vấn ta xóa đi phần tử mình tìm được là xong, như vậy chặt nhị phân của bạn sẽ không bao giờ tìm được vị trí đã bị chiếm!!!
+ Vậy với bãi đỗ xe làm 1 vòng tròn, nếu không tìm thấy thì ta đơn giản là quay về vị trí nhỏ nhất còn trong set, đó là set.begin(), rồi xóa đi là được
+ Độ phức tạp : NlogN, ngoài ra set còn hỗ trợ lower_bound nữa, quá tiện lợi!
# Pseudo code
```
for ( int i : truyvan ) {
it = s.lower_bound(i)
if it == s.end() -> it = s.begin()
s.erase(i)
```
kevinPhan
Created at
7 likes
datduong
Created at
2 likes
dsadsadas
Created at
2 likes