笔试时间：2023年9月14日 秋招

备注：第三题题解待更新。

第一题

题目：最优化存储

支付宝服务亿级消费者，每个支付宝的用户有自己独特的信息，假设每个会员存储的成本为ai，现在有n个会员，和m块存储容器，希望用该容器存储更多的会员信息。存储优化是个相当复杂的过程，为了简化问题，存储规则如下:

1、每个会员的存储成本可以用长度ai的线段表示。存储容器m块，每块可以用一段线段bi表示；

2、存诸容器有个特性，如果会员i存储在容器中间位置(非两端即为中间)，存储成本为ai本身，但是线段容器两端有存储压缩技术，存储在靠两端位置的会员存储成本可以压缩到一半，即ai/2，而且每个会员只能压缩一次。

现在n个会员，每个会员存储成本为ai，以及有m块存储资源bi，希望你做存储优化，求能存储最大的会员数量是多少？

输入描述

第一行输入两个正整数n和m，用空格隔开。代表会员数量、最大存储空间；

第二行输入n个正整数ai，代表每个会员的存储成本；

第三行输入m个正整数bi，代表每块存储容器的长度。

1 <= n, m <= 10^5

1 <= ai <= 2

1<= bi <= 2

输出描述

一个整数，代表最大的信息量之和。

样例输入

5 2

1 2 2 1 2

2 1

样例输出

4

提示

选择前四个会员，将第二个和第三个的会员信息放在第一个容器的两端位置，将第一个和第四个会员的信息放在第二个容器的两端位置

参考题解

贪心，先把会员长度1的贪心，再对会员长度2的贪心。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
using namespace std;

const int MAX_N = 3; // 最大数量
int s[MAX_N], t[MAX_N]; // 计数数组

int main() {
    int n, m, x;
    cin >> n >> m;

    // 初始化计数数组
    for (int i = 0; i < n; i++) {
        cin >> x;
        s[x]++;
    }
    for (int i = 0; i < m; i++) {
        cin >> x;
        t[x]++;
    }

    int ans = 0;

    // 处理s[1]
    while (s[1] > 0) {
        if (t[1] > 0) {
            int x = min(2, s[1]);
            ans += x;
            s[1] -= x;
            t[1]--;
        } else if (t[2] > 0) {
            int x = min(3, s[1]);
            if (x == 1 && s[2] > 0) {
                ans++;
                s[2]--;
            }
            ans += x;
            s[1] -= x;
            t[2]--;
        } else {
            break;
        }
    }

    // 处理s[2]
    while (s[2] > 0) {
        if (t[1] > 0) {
            ans++;
            s[2]--;
            t[1]--;
        } else if (t[2] > 0) {
            int x = min(2, s[2]);
            ans += x;
            s[2] -= x;
            t[2]--;
        } else {
            break;
        }
    }

    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 MAX_N = 3;
        int[] s = new int[MAX_N];
        int[] t = new int[MAX_N];

        int n = scanner.nextInt();
        int m = scanner.nextInt();

        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            s[x]++;
        }

        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            t[x]++;
        }

        int ans = 0;

        while (s[1] > 0) {
            if (t[1] > 0) {
                int x = Math.min(2, s[1]);
                ans += x;
                s[1] -= x;
                t[1]--;
            } else if (t[2] > 0) {
                int x = Math.min(3, s[1]);
                if (x == 1 && s[2] > 0) {
                    ans++;
                    s[2]--;
                }
                ans += x;
                s[1] -= x;
                t[2]--;
            } else {
                break;
            }
        }

        while (s[2] > 0) {
            if (t[1] > 0) {
                ans++;
                s[2]--;
                t[1]--;
            } else if (t[2] > 0) {
                int x = Math.min(2, s[2]);