Hướng dẫn giải của Bedao Mini Contest 25 - Vấn đề kỹ năng
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.
Subtask 1: ~N \le 20~
We use recursion and keep track of the number of people processed, the number of coders, and the number of testers.
Subtask 2: ~N \le 1000~
This is a transformation of the classic greedy problem ACMNB on VNOI. Consider the problem with ~n + m~ people, initially, we assign all these people as coders with values ~a_i~.
When the ~i~-th person is a tester, the cost changes by an amount of ~b_i - a_i~. We need to select the ~m~ largest values of ~b_i - a_i~ to add to the total, so we simply sort in ~O(N \log N)~ and take the ~m~ largest values. For each missing position, we do this in ~O(N \log N)~, thus the complexity is ~O(N^2 \log N)~.
Subtask 3: ~N \le 5000~:
We have a dynamic programming solution as follows:
Define the states ~f(i, x)~ as considering prefix[~1~ : ~i~] and selecting ~x~ coders, ~g(i, x)~ as considering suffix[~i~ : ~N~] and selecting ~x~ testers.
For each ~i~, we merge the two states ~f(i - 1,x)~ and ~g(i + 1, N - x)~ to get the answer.
The complexity is ~O(n^2)~.
Subtask 4,5
~N \le 5 \cdot 10^5~: The main idea of the solution lies in subtask 2.
The solution presents a suitable data structure for this subtask, which allows:
Adding/removing elements
Calculating the sum of the ~k~ largest numbers
The solution presents an algorithm using std :: multiset, other algorithms using Segment/Fenwick tree or Policy-based Data Structures with similar complexity will be omitted and considered as an exercise for the reader.
We use ~2~ sets: one set ~A~ contains the elements of the ~k~ largest elements, and a set ~B~ contains the elements that are "waiting," meaning they are behind the ~k~ largest elements. We also maintain a variable ~s~ representing the sum of the first ~k~ elements.
When adding an element ~x~, we simply add it to set ~A~ and add ~x~ to ~s~. If set ~A~ has more than ~k~ elements, we remove the smallest from ~A~ and add it to ~B~.
When removing ~x~, if ~B~ contains ~x~, we remove ~x~ from ~B~ once. Otherwise, if ~A~ contains ~x~, we remove it from ~A~. After removal, if ~A~ has fewer than ~k~ elements, we take some of the largest from ~B~ to fill ~A~ back to ~k~ elements.
Additionally, there exists another solution that does not use a data structure but instead sorts the elements by the difference ~a_i - b_i~ in descending order. The details of the implementation are left to the reader.
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 5e5 + 5, MOD = 1e9 + 7; int n, m, a[N], b[N], ans[N]; void solve(){ cin >> n >> m; for(int i = 1; i <= n + m + 1; i++) cin >> a[i]; for(int i = 1; i <= n + m + 1; i++) cin >> b[i]; vector<int> id(n + m + 2, 0); iota(id.begin() + 1, id.end(), 1); sort(id.begin() + 1, id.end(), [](int x, int y){ return a[x] - b[x] > a[y] - b[y]; }); int suma = 0, sumb = 0; for(int i = n + m + 1; i >= n + 1; i--){ sumb += b[id[i]]; } for(int i = n + 1; i >= 1; i--){ suma += a[id[i]]; } for(int i = 1; i <= n + m + 1; i++){ ans[id[i]] = suma - a[id[min(i, n + 1)]] + sumb - b[id[max(i, n + 1)]]; } for(int i = 1; i <= n + m + 1; i++) cout << ans[i] << ' '; cout << '\n'; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //io(); int t = 1; cin >> t; while(t--){ solve(); } return 0; }
Bình luận
bài này giống bài 1976C trên Codeforces :V
ai code subtask cuối bằng multiset chưa ạ cho em xin với
sao sol toàn tiếng Anh thế ạ 🥲