P12342 [蓝桥杯 2025 省 B/Python B 第二场] 数列差分

题目描述

小蓝有两个长度均为 $n$ 的数列 A={a1,a2,⋯ ,an}A=\{a_1, a_2, \cdots, a_n\}A={a1​,a2​,⋯,an​} 和 B={b1,b2,⋯ ,bn}B=\{b_1, b_2, \cdots, b_n\}B={b1​,b2​,⋯,bn​}，将两个数列作差定义为 C=A−B={c1=a1−b1,c2=a2−b2,⋯ ,cn=an−bn}C=A-B=\{c_1=a_1-b_1, c_2=a_2-b_2, \cdots, c_n=a_n-b_n\}C=A−B={c1​=a1​−b1​,c2​=a2​−b2​,⋯,cn​=an​−bn​}。小蓝将对数列 $B$ 进行若干次操作，每次操作可以将数列 $B$ 中的任意一个数更改为任意一个整数。在进行完所有操作后，小蓝可以按任意顺序将数列 $B$ 重排，之后再计算数列 $C$。小蓝想知道，最少操作多少次可以使得数列 $C$ 中的所有数都为正整数。

输入格式

输入的第一行包含一个正整数 $n$；

第二行包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n$，相邻整数之间使用一个空格分隔。

第三行包含 $n$ 个整数 $b_1,b_2,\cdots ,b_n$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

4
22 31 12 14
3 19 27 44

输出 #1

1

说明/提示

样例说明

其中一种方案：将 $44$ 改为 $0$，重新排列 $B$ 为 {19,27,3,0}\{19, 27, 3, 0\}{19,27,3,0}，使得数列 C={3,4,9,14}C=\{3, 4, 9, 14\}C={3,4,9,14} 均为正整数。

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$n\le 10$；
• 对于所有评测用例，$1\le n\le 10^5$，$-10^9\le a_i\le 10^9$，$-10^9\le b_i\le 10^9$。

题解：
题目说了很多，其实就要求a数组里的对应的数字大于b数组里对应的数字。首先就是要排序，然后a数组b数组同时从后往前遍历，遇到不符合条件的数字就记录个数就可以了

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n;i++){
		cin>>b[i];
	}
	sort(a,a+n);
	sort(b,b+n);
	int s1=n-1,s2=n-1,ans=0;
	while(s2>=0){
		if(a[s1]>b[s2]){
			s1--;
			s2--;
		}else{
			s2--;
			ans++;
		}
	}
	cout<<ans;
	return 0;
}