P12342 [蓝桥杯 2025 省 B/Python B 第二场] 数列差分
原题链接
题目范围
\(1 \leq n \leq 10^5\)，\(-10^9 \leq a_i \leq 10^9\)，\(-10^9 \leq b_i \leq 10^9\)。
解题思路
求最少修改，等价于最多保留。
将数组 a 和 b 排序，用双指针贪心求出有多少个 \(b_j\) 能找到严格大于它的 \(a_i\)，这些 \(b_j\) 保留，那么答案即为 \(n - \text{保留数}\)。
双指针原理分析：a、b 排序后，指针 i、j 分别指向首位。
- 如果
a[i] > b[j]，则a[i]和b[j]匹配，这个 \(b_j\) 保留，keep++，i++，j++ - 否则，说明
a[i]不够大（a[i] <= b[j]），则i++继续寻找更大的元素
复杂度分析
时间复杂度：\(O(n \log n)\)（主要来自排序）
空间复杂度：\(O(n)\)（存储数组）
代码实现
void solve(){int n;cin>>n;vector<int>a(n),b(n);rep(i,0,n) cin>>a[i];rep(i,0,n) cin>>b[i];int keep=0,i=0,j=0;sort(all(a));sort(all(b));while(i<n&&j<n){if(a[i]>b[j]) {keep++;i++;j++;}else {i++;}}cout<<n-keep<<'\n';
}