第十六届蓝桥杯 2025 C/C++组 数列差分

目录

题目：

题目描述：

题目链接：

思路：

核心算法：

思路详解：

代码：

代码详解：

---

题目：

题目描述：

题目链接：

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;
}