目录
题目：
题目描述：
题目链接：
P12342 [蓝桥杯 2025 省 B/Python B 第二场] 数列差分 - 洛谷
思路：
核心算法：
排序+双指针
思路详解：
第一眼看到题目还以为考察的是差分，结果发现题目和差分没啥关系
首先为什么要对a，b数组进行排序？由题定义了cn=an-bn，问最少操作多少次可以使得数列c中的所有数都为正整数，这里并不存在田忌赛马的情况，想要操作次数尽可能少所以肯定是一一对应：大的减大的，小的减小的
然后就来分析操作，我们从a，b中最大的数开始比，如果此时an>bn，那么符合题目要求再比较an-1和bn-1即可。如果此时an<=bn，那么我们要对bn的值进行调整了，由题操作可以把bn的值改为任意整数（那肯定把bn改的越小越好，这样改完之后b数组排序这个值就会排到最前面），当然这个改值再重新排序的过程自己在脑海中有个印象就好，实际编程不需要实现。那么此时b数组要对应的最大值就改变了（变成了一开始排序好的bn-1），再比较an和bn-1。后续其实就是这两种情况的循环了，循环结束的条件就是把一开始排序好的b数组里全部的数值都比较完（那些操作完的值不用管）
上述过程用双指针即可实现，具体怎么实现可以结合下图草稿的模拟样例全过程
代码：
代码详解：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N];
int b[N];
int cnt;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) //按题意从a1,b1开始,初始索引i=1
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
}
sort(a+1,a+1+n); //对a,b数组进行排序,不要忘记索引从1开始
sort(b+1,b+1+n);
int i=n; //定义i指针指向a数组最大的值的索引
int j=n; //定义j指针指向b数组最大的值的索引
while(j!=0) //模拟结束的条件是j==0,因为当b数组的最后一个数(j==1)比较之后j--得到0
{
if(a[i]>b[j]) //满足相减为正整数
{
i--;
j--;
}
else //不满足相减为正整数,此时一定会操作把j指针指向的值调整为越小的值越好
{
//b[j]=-1e9-1; //单纯为了更好理解,实际记录操作次数即可
j--; //b[j]调整之后肯定就不再是b数组中的最大值,再比较就要重新找调整后的b数组的
//最大值,所以j--
cnt++; //操作次数+1
}
}
cout<<cnt<<endl;
return 0;
}