笔试时间：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) {