Approach
Sorting and greedy selection
For ABC212 C — Min Difference, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 44 lines of C++ from the credited upstream file abc212_c.cpp.
- The implementation visibly relies on sequence storage.
- 3 loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <algorithm>2#include <cmath>3#include <iostream>4#include <vector>5 6using namespace std;7using ui = unsigned int;8 9int main() {10 ui n, m;11 cin >> n >> m;12 13 vector<ui> a(n, 0);14 for (auto& aa : a) cin >> aa;15 sort(a.begin(), a.end());16 17 vector<ui> b(m, 0);18 for (auto& bb : b) cin >> bb;19 sort(b.begin(), b.end());20 21 ui ni = 0;22 ui mi = 0;23 ui ans = max((a[n - 1] > b[0] ? a[n - 1] - b[0] : b[0] - a[n - 1]),24 (b[m - 1] > a[0] ? b[m - 1] - a[0] : a[0] - b[m - 1]));25 while (ni < n - 1 || mi < m - 1) {26 if (a[ni] > b[mi]) {27 ans = min(ans, a[ni] - b[mi]);28 if (mi == m - 1)29 ni = min(ni + 1, n - 1);30 else31 mi = min(mi + 1, m - 1);32 } else {33 ans = min(ans, b[mi] - a[ni]);34 if (ni == n - 1)35 mi = min(mi + 1, m - 1);36 else37 ni = min(ni + 1, n - 1);38 }39 }40 41 cout << ans << endl;42 43 return 0;44}