Hướng dẫn cho Chơi nhạc (OLP MT&TN 2021 CT)
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)
\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)
\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)
\(\color{orange}{\text{Hướng dẫn}}\)
-
Gọi \([l_i ; r_i]\) là khoảng nghe thấy của học sinh thứ \(i\). Ta có \([l_i ; r_i] = [p_i - d_i ; p_i + d_i]\)
-
Gọi \(X\) là vị trí ta chọn, thí giá trị của vị trí đó \(f(X) = \overset{n}{\underset{i = 1}{\Sigma}}(\overset{r_i}{\underset{p = l_i}{min}}(|p - X|) \times t_i)\)
-
Để tính nhanh đoạn \(V = (\overset{r_i}{\underset{p = l_i}{min}}(|p - X|) \times t_i)\)
\(X \leq l_i \leq r_i\) thì \(V = (l_i - X) \times t_i\)
\(l_i \leq X \leq r_i\) thì \(V = 0\)
\(l_i \leq r_i \leq X\) thì \(V = (X - r_i) \times t_i\)
- Để giảm độ phức tạp việc duyệt \(X = min(l_i) \rightarrow max(r_i)\)
Với \(S\) là tập các vị trí \(l_i, r_i\), hay \(S = \big((l_i)\ \ |\ \ 1 \leq i \leq n\big) \cup \big((r_i)\ \ |\ \ 1 \leq i \leq n\big)\)
Ta chứng minh với mọi giá trị \(X \notin S\) sẽ không đưa ra giá trị \(f(X)\) tối ưu
- Để giảm độ phức tạp việc duyệt \(X \in S\), ta dùng sweepline
Chia ra 3 tập, gồm các đoạn bên trái \(X\), chứa \(X\), bên phải \(X\)
Tính giá trị cần thiết để dịch chuyển tất cả các đoạn của một tập sao cho tất cả chứa \(X\)
Tính giá trị hệ số để di chuyển toàn bộ đoạn trong một tập đi một đơn vị
\(\color{goldenrod}{\text{Tiếp cận}}\)
- Thứ tự duyệt: Duyệt \(X\) tăng dần
Ta sẽ tạo 3 tập là \(ls, ms, rs\) chứa các đoạn bên trái \(X\), chứa \(X\), bên phải \(X\)
Ta sẽ tạo 3 giá trị là \(lv, mv, rv\) tức là tổng giá trị của các đoạn trong tập \(ls, ms, rs\) với \(X\) (tổng chi phí để dịch tất cả các đoạn sao cho tất cả chứa \(X\))
Ta sẽ tạo 3 giá trị là \(lt, mt, rt\) tức là tổng hệ số của các đoạn trong tập \(ls, ms, rs\) vói \(X\) (chi phí để dịch tất cả đoạn trong 1 tập đi 1 đơn vị)
Ban đầu khởi tạo là mọi đoạn đều thuộc tập bên phải cùng \(rs\)
- Khi duyệt tới \(X\) tiếp theo, gọi \(gap\) là khoảng cách này
Bên phải bị hụt mất một giá trị bằng \(gap \times rt\) (vi \(X\) tới gần hơn mọi đoạn trong \(rs\) nên giảm bớt chi phí lại)
Bên trái được thêm một giá trị bằng \(gap \times rt\) (vì \(X\) tiến xa khỏi mọi đoạn trọng \(ls\) nên tăng thêm chi phí đi)
Các đoạn ở tập \(rs\) năm bên trái \(X\) mình sẽ chuyển xuống tập \(ms\), và giảm bớt chi phí đoạn này lại (vì các đoạn trong \(ms\) đều chứa \(X\) không mất chi phí nhưng trước đó tính trong tập \(rs\))
Các đoạn ở tập \(ms\) năm bên trái \(X\) mình sẽ chuyển xuống tập \(ls\), và tăng thêm chi phí đoạn này đi (vì các đoạn trong \(Ls\) đều chứa \(X\) mất chi phí nhưng trước đó không tính trong tập \(ms\))
Để tiện xóa các đoạn có giá trị nhỏ hơn \(X\) tại thời điểm bất kì, ta dùng \(std::set\) sắp xếp theo thứ tự của điểm
....
\(\color{purple}{\text{Độ phức tạp}}\)
- Sweepline, tính toán, sắp xếp và truy vấn bằng set mất \(O(n\ log\ alphabet)\)
\(\color{green}{\text{Code tham khảo }}\): Toán, Sweepline
\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n\ log\ alphabet)\ \color{purple}{\text{thời gian}}\ ||\ O(n\ log\ alphabet)\ \color{purple}{\text{bộ nhớ}}}}\)
#include <iostream>
#include <set>
using namespace std;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
typedef long long ll;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int LIM = 1e6 + 16;
struct Student
{
int p, t, d, l, r;
Student(int p = 0, int t = 0, int d = 0)
: p(p), t(t), d(d), l(p - d), r(p + d) {}
};
struct Node
{
int p, i;
Node (int p = 0, int i = 0)
: p(p), i(i) {}
bool operator < (const Node &o) const
{
return (p != o.p) ? (p < o.p) : (i < o.i);
}
};
int n;
Student a[LIM];
int input()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
int p, t, d;
cin >> p >> t >> d;
a[i] = Student(p, t, d);
}
return 0;
}
int solve()
{
set<int> S;
for (int i = 1; i <= n; ++i)
{
S.insert(a[i].l);
S.insert(a[i].r);
}
int pre_X = *S.begin();
/// All X not in S provides larger f(X) which we dont need to care
ll lt = 0, mt = 0, rt = 0;
ll lv = 0, mv = 0, rv = 0;
set<Node> ls, ms, rs;
for (int i = 1; i <= n; ++i)
{
int gap = (a[i].l - pre_X);
rv += 1LL * gap * a[i].t;
rt += a[i].t;
/// pre_X < a[i].l <= a[i].r
rs.insert(Node(a[i].l, i));
}
///
/// a[i].l = a[i].p - a[i].d
/// a[i].r = a[i].p + a[i].d
///
/// Left.r < X < Right.l
/// Middle.l <= X <= Middle.r
///
/// => f(Left) = Sigma((X - a[i].r) * a[i].t)
/// => f(Middle) = 0
/// => f(Right) = Sigma((a[i].l - X) * a[i].t)
///
// cout << "AT (-1):\n";
// cout << lv << ' ' << lt << " | L[] = "; for (const Node &e : ls) cout << e.i << ' '; cout << endl;
// cout << mv << ' ' << mt << " | M[] = "; for (const Node &e : ms) cout << e.i << ' '; cout << endl;
// cout << rv << ' ' << rt << " | R[] = "; for (const Node &e : rs) cout << e.i << ' '; cout << endl;
// cout << "VAL = " << lv + rv << endl;
// cout << "=============================\n";
int gap = 0;
ll res = +LINF;
for (int X : S)
{
gap = X - pre_X;
rv -= 1LL * gap * rt;
while (rs.size() && rs.begin() -> p <= X)
{
int p = rs.begin() -> p;
int i = rs.begin() -> i;
int gap = X - p;
rv += 1LL * gap * a[i].t;
rt -= a[i].t;
/// a[i].l <= X <= a[i].r
rs.erase(rs.begin());
ms.insert(Node(a[i].r, i));
}
lv += 1LL * gap * lt;
while (ms.size() && ms.begin() -> p < X)
{
int p = ms.begin() -> p;
int i = ms.begin() -> i;
int gap = X - p;
lv += 1LL * gap * a[i].t;
lt += a[i].t;
/// a[i].l <= a[i].r < X
ms.erase(ms.begin());
// ls.insert(Node(a[i].r, i));
}
// cout << "AT (" << X << "):\n";
// cout << lv << ' ' << lt << " | L[] = "; for (const Node &e : ls) cout << e.i << ' '; cout << endl;
// cout << mv << ' ' << mt << " | M[] = "; for (const Node &e : ms) cout << e.i << ' '; cout << endl;
// cout << rv << ' ' << rt << " | R[] = "; for (const Node &e : rs) cout << e.i << ' '; cout << endl;
// cout << "VAL = " << lv + rv << endl;
// cout << "=============================\n";
minimize(res, lv + rv);
pre_X = X;
}
cout << res;
return 0;
}
int main()
{
ios::sync_with_stdio(NULL);
cin.tie(NULL);
input();
solve();
return 0;
}
/*
6
2 3 2
2 5 1
2 1 0
4 4 3
4 2 2
5 1 2
0 1 2 3 4 5 6 7
|---|---|---|---|---|---|---|
3
|-------o-------|
5
|---o---|
1
|o|
4
|-----------o-----------|
2
|-------o-------|
1
|-------o-------|
|---|---|---|---|---|---|---|
0 1 2 3 4 5 6 7
AT (-1):
0 0 | L[] =
0 0 | M[] =
18 16 | R[] = 1 2 4 3 5 6
VAL = 18
=============================
AT (0):
0 0 | L[] =
0 0 | M[] = 1
18 13 | R[] = 2 4 3 5 6
VAL = 18
=============================
AT (1):
0 0 | L[] =
0 0 | M[] = 2 1 4
5 4 | R[] = 3 5 6
VAL = 5
=============================
AT (2):
0 0 | L[] =
0 0 | M[] = 3 2 1 5 4
1 1 | R[] = 6
VAL = 1
=============================
AT (3):
1 1 | L[] = 3
0 0 | M[] = 2 1 5 4 6
0 0 | R[] =
VAL = 1
=============================
AT (4):
7 6 | L[] = 3 2
0 0 | M[] = 1 5 4 6
0 0 | R[] =
VAL = 7
=============================
AT (6):
25 9 | L[] = 3 2 1
0 0 | M[] = 5 4 6
0 0 | R[] =
VAL = 25
=============================
AT (7):
36 11 | L[] = 3 2 1 5
0 0 | M[] = 4 6
0 0 | R[] =
VAL = 36
=============================
*/
Bình luận