笔试时间:2023年9月14日 秋招 第一题 题目:小红的逆序对 小红现在有一个长度为n的数组a1,a2,...,an,她希望这个数组出现至少一个逆序对。每一次她可以进行如下两种操作之一: 1、选择一个元素ai,对ai加上x; 2、选择一个元素ai,对ai减去y。 至少需要多少次操作才能够保证数组出现了至少一个逆序对?这里的一个逆序对是指,存在一个下标对(i,j),同时满足1 <= i < j<=n和ai > aj。 输入描述 第一行三个整数n,x,y,表示数组的大小和x,y的值; 第二行n个整数,表示数组a1,a2,..,an。 2 <= n <= 10^5 -10^9 <= ai <= 10^9 1 <= x,y <= 10^9 输出描述 输出一个整数表示答案。 样例输入 示例一: 3 1 2 1 3 5 示例二: 4 5 7 4 6 10 9 样例输出 示例一: 2 示例二: 0 参考题解 如果数组本身存在逆序对,则需要进行0次操作,如果不存在逆序对,则说明数组是有序的,因为要考虑到操作最少,所以选择值最接近的两个数进行操作。遍历数组,两两进行+x或者-y,然后求min。 C++:[此代码未进行大量数据的测试,仅供参考] #include <iostream>#include <vector>#include <algorithm>using namespace std;int main() { int n, x, y; cin >> n >> x >> y; int o = max(x, y); vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int d = INT_MAX; for (int i = 1; i < n; i++) { d = min(d, a[i] - a[i - 1]); } int ans = (d < 0) ? 0 : (d / o) + 1; cout << ans << endl; return 0;} Java:[此代码未进行大量数据的测试,仅供参考] import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int x = scanner.nextInt(); int y = scanner.nextInt(); int o = Math.max(x, y); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); } int d = Integer.MAX_VALUE; for (int i = 1; i < n; i++) { d = Math.min(d, a[i] - a[i - 1]); } int ans = (d < 0) ? 0 : (d / o) + 1; System.out.println(ans); }} Python:[此代码未进行大量数据的测试,仅供参考] def main(): n, x, y = map(int, input().split()) max_interval = max(x, y) positions = list(map(int, input().split())) min_distance = min(positions[i] - positions[i - 1] for i in range(1, n)) ans = 0 if min_distance < 0 else min_distance // max_interval + 1 print(ans)if __name__ == "__main__": main() 第二题 题目:小红的匹配 小红有1到n这n个数字,n是偶数。她想将这n个数字两两匹配,比如将ai和aj匹配,i!=y,需要保证 (ai+k) x aj 是4的倍数,即(ai+k) x aj%4= 0,其中k是一个整数,每个数字只能匹配一次。 请问小红能否完成匹配,如果可以,输出匹配的方案。 输入描述 第一行两个整数n和k,表示数字的个数和k的值,保证n是一个偶数。 1 <= n,k <= 10^5 输出描述 如果能完成匹配,输出YES,然输出n/2行,每行两个整数ai和aj,表示匹配的两个数字。如果不能完成匹配,输出NO。 样例输入 4 2 样例输出 YES 2 1 3 4 提示 (2 + 2)*1 = 4是4的倍数,(3 + 2) 4 = 20是4的倍数。 参考题解 k是奇数,k是2的倍数,但不是4的倍数,k是4的倍数。分类讨论,注意考虑所有情况。 C++:[此代码未进行大量数据的测试,仅供参考] #include <iostream>#include <vector>using namespace std;const int MAX_N = 100004;int main() { int n, k; cin >> n >> k; vector<int> a(n), b(n); int m = n / 2; int flag = 0; if (k % 2 == 1) {