My $$$O(n^2)$$$ Greedy Approach to Problem 2237B and Why It Works
Разница между en1 и en2, 1138 символ(ов) изменены
### Solution : [problem:2237B]↵
↵
#### Hint 01↵
↵
We are given that the final array $b$ is strictly increasing ($b_1 < b_2 < \dots < 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 02↵
↵
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.↵
↵
---↵
↵
### 
SolutionGreedy Approach↵
↵
Since $b$ is strictly increasing
, i.e.  ($b_1 < b_2 < \cdots < b_n$), the condition $a_j \le b_i$ becomes easier to satisfy as $i$ increases. Therefore, it is optimalbest 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 selectworks perfectly because:↵
↵
1. Choos
ing 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, tleaves later elements available for the larger values of $b$ coming up next.↵
2. T
aking the leftmost oneavailable element minimizes the distance the chosen element must travel, which directly helps minimize the number of adjacent sit has to travel, which keeps the number of swaps as small as possible.↵
↵
### Counting S
waps.↵
↵
Suppose the element chosen for $b_i$ is 
located at position $j$. To move it into its required positioncorrect spot, it must swap passt every still-unused element located to its left. Positionelement to its left that hasn't been used yet. Elements that havare already been matched do non't countribute, sinc because they have effectivelalready been removed from the sequence. Thereforeout of the way.↵
↵
So
, the number of swaps contributed byneeded for position $j$ is exactsimply the number of **unmatched positions before it, namely↵
$$↵
|{,
**:↵
↵
$$|\{
k < j \mid k \text{ has not been matched yet},\}|.↵
$$↵
If we maintain all currently unused positions ↵
While this can be optimized us
ing 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** (Binary Indexed Tree) to query prefix sums in $O(\log n)$ time, the constraints here allow us to just use a simple loop to count unmatched elements in $O(n)$ time per step. Summing these contributions over all matched positions yields the minimum number of adjacent swaps required.↵
### Implementation↵
↵
↵
~~~~~
unts up for all elements gives us our final answer. If we ever find a $b_i$ that cannot match with any available $a_j$, it's impossible, so we output `-1`.↵
↵
```cpp
↵
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;{↵
            ++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$, 
an $n^2$ operationsapproach easily runs well within the 1.5-second time limit.↵
* **Space Complexity:** $\mathcal{O}(n)$ to store
 the arrays and the tracking (`seen`) array.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский testUser44 2026-06-19 09:16:09 5
en2 Английский testUser44 2026-06-19 09:15:29 1138
en1 Английский testUser44 2026-06-19 08:27:25 2830 Initial revision (published)