Solution : 2237B - Раздражительный призрак
Hint 1
We are given that the final array $$$b$$$ is strictly increasing ($$$b_1 \lt b_2 \lt \dots \lt b_n$$$). We construct this final array from left to right. Since we can only add ducks, an initial pile $$$a_j$$$ can be transformed into a target pile $$$b_i$$$ if and only if $$$a_j \le b_i$$$.
Hint 2
If we decide which elements of $$$a$$$ map to which elements of $$$b$$$, the number of adjacent swaps required to reorder them into their final positions is exactly the number of inversions created by our choice.
Solution
Since $$$b$$$ is strictly increasing, i.e. $$$b_1 \lt b_2 \lt \cdots \lt b_n$$$, the condition $$$a_j \le b_i$$$ becomes easier to satisfy as $$$i$$$ increases. Therefore, it is optimal to process the elements of $$$b$$$ from left to right. For each $$$b_i$$$, we choose the leftmost unused position $$$j$$$ such that $$$a_j \le b_i$$$. This greedy choice is optimal because selecting an earlier valid element can never make future matchings harder: any element appearing later in $$$a$$$ remains available for the larger values of $$$b$$$ that will be processed afterwards. Furthermore, among all feasible choices, taking the leftmost one minimizes the distance the chosen element must travel, which directly helps minimize the number of adjacent swaps.
Suppose the element chosen for $$$b_i$$$ is located at position $$$j$$$. To move it into its required position, it must pass every still-unused element located to its left. Positions that have already been matched do not contribute, since they have effectively been removed from the sequence. Therefore, the number of swaps contributed by position $$$j$$$ is exactly the number of unmatched positions before it, namely
If we maintain all currently unused positions in a Fenwick Tree, this value can be obtained as the prefix sum on the range $$$[1, j-1]$$$. After matching position $$$j$$$, we remove it from the data structure. Summing these contributions over all matched positions yields the minimum number of adjacent swaps required.
Implementation
int n, ans = 0;
cin >> n;
vector<int> a(n), b(n), seen(n + 1);
for (int& it : a) cin >> it;
for (int& it : b) cin >> it;
for (int i = 0; i < n; ++i) {
bool ok = false;
for (int j = 0; j < n; ++j) {
if (a[j] <= b[i] && !seen[j]) {
ok = true;
seen[j] = 1;
break;
}
if (!seen[j]) ++ans;
}
if (!ok) {
cout << -1 << endl;
return;
}
}
cout << ans << endl;
Complexity Analysis
- Time Complexity: $$$\mathcal{O}(n^2)$$$ per test case. Since $$$\sum n \le 2000$$$, $$$n^2$$$ operations easily run within 1.5-sec.
- Space Complexity: $$$\mathcal{O}(n)$$$ to store



