笔试时间：2023年3月12日 春招实习

第一题

题目：飞机大战

多多最近下载了一款飞机大战的游戏,多多可以通过游戏上的不同发射按键来控制飞机发射子弹：

按下A键,飞机会发射出2枚子弹,每个子弹会对命中的敌人造成1点固定伤害，但不能作用于同个敌人。

按下B键,飞机会发射出1枚子弹,子弹会对命中的敌人造成巨额伤害并瞬间将其秒杀。

多多是个游戏高手,总是能操控子弹命中想要命中的敌人。这个游戏—共有T价关卡,消灭当前关卡全部敌人后,发射出去多余的子弹会消失,游戏会自动进入下一个关卡。假设每个关卡都会在屏幕中同时出现N个敌人,这N个敌人所能承受的伤害也已经知道。多多想知道,每个关卡自己最少按几次发射按键就可以将敌人全部消灭?

输入描述

第一行输入一个固定数字T表示关卡的总数量,N（1<=N<=200）表示每个关卡出现的敌人数量。

接下来T行，每行有N个数字D1,D2, ..... Dw（1<= Di <= 200)分别表示这N个敌人所能承受的伤害。

输出描述

结果共有N行，每行一个数字,分别表示对于这个关卡,最少按几次发射按键就可以将敌人全部消灭。

示例输入

3 3

1 2 1

2 3 2

1 2 3

示例输出

2

3

3

说明

游戏共有3个关卡,每个关卡会出现3个敌人。

第一个关卡,先按下A建控制子弹消灭第1个和第3个敌人后,再按下B键消灭第二个敌人。所以最少按2次。

第二个关卡,按下3次B键分别消灭这3个敌人。

第三个关卡,按下3次B键分别消灭这3个敌人。也可以按3次A建,敌人剩余承受伤害的变化为:[1, 2，3]->[1,1,2]→>[,0, 1] -> [0,0, 0]

参考题解

贪心。

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int N = sc.nextInt();

        for (int t = 0; t < T; t++) {
            int[] D = new int[N];
            for (int i = 0; i < N; i++) {
                D[i] = sc.nextInt();
            }

            Arrays.sort(D);

            int cnt = 0;
            int i = 0;
            while (i + 1 < N) {
                if (D[i] == 1 && D[i + 1] == 1) {
                    cnt++;
                    i += 2;
                } else {
                    break;
                }
            }
            cnt += N - i;
            System.out.println(cnt);
        }
    }
}

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

T, N = map(int, input().split(" "))
for _ in range(T):
    D = [int(c) for c in input().split(" ")]
    D.sort()
    cnt = 0
    i = 0
    while i + 1 < N:
        if D[i] == D[i + 1] == 1:
            cnt += 1
            i += 2
        else:
            break
    cnt += N - i
    print(cnt)

第二题

题目：团建规划

又到了团建的时间,多多君负责安排这次的团建活动。多多君准备了三个活动（分别编号A、B和C)，每个活动分别有人数上限以及每个人参加的费用。参加团建的有N个人(分别编号1~N）,每个人先投票选择若干个意向的活动,最终每个人只能参加其中一个。多多君收集完投票结果后,发现如何安排成为了大难题:如何在满足所有人的意向的情况下,使得活动的总费用最少。于是多多君找到了擅长编程的你,希望你能帮助找到个合理的团建计划。

输入描述

第一行,一个整数N,代表准备参加活动的人数。(1<=N<=100 )

接下来N行,每行一个由"ABC"组成的字符串,其中第i行表示第i个人投票了哪几个活动。

(输入保证字符串非空,且由大写的"ABC"字符组成)

最后3行,每行两个整数,分别表示三个活动的人数上限以及每个人参加的费用。

(人数上限以及参与活动的费用均为不超过100的正整数)

输出描述

输出共2行

如果能满足所有人的要求,第一行输出"YES”,第二行输出最少的总费用。

如果不能满足所有人的要求,第一行输出"NO，第二行输出最多能满足多少人。

示例输入

示例输入一：

5

A

B

C

AB

ABC

2 1

2 2

2 3

示例输入二：

5

A

B

C

AB

AB

1 1

2 2

3 3

示例输出

示例输出一：

YES

9

示例输出二：

NO

4

参考题解

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

#include <iostream>
#include <vector>
#include <deque>
#include <unordered_map>

const int INF = std::numeric_limits<int>::max();

struct Edge {
    int from, to, capacity, weight;
    Edge(int u, int v, int c, int w) : from(u), to(v), capacity(c), weight(w) {}
};

std::vector<std::vector<int>> graph;
std::vector<Edge> edges;

void add_edge(int u, int v, int c, int w) {
    edges.push_back(Edge(u, v, c, w));
    edges.push_back(Edge(v, u, 0, -w));
    graph[u].push_back(edges.size() - 2);
    graph[v].push_back(edges.size() - 1);
}

std::tuple<bool, std::vector<int>, std::vector<int>> spfa(int source, int sink, int n) {
    std::vector<int> dist(n + 1, INF);
    std::vector<bool> visited(n + 1, false);
    std::vector<bool> in_queue(n + 1, false);
    std::vector<int> pre_edge(n + 1, -1);
    dist[source] = 0;
    std::deque<int> q;
    q.push_back(source);
    in_queue[source] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        in_queue[u] = false;
        visited[u] = true;
        for (int i : graph[u]) {
            int v = edges[i].to, c = edges[i].capacity, w = edges[i].weight;
            if (c > 0 && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pre_edge[v] = i;
                if (!in_queue[v]) {
                    q.push_back(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    return std::make_tuple(visited[sink], dist, pre_edge);
}

std::pair<int, int> mcmf(int source, int sink, int n) {
    int max_flow = 0, min_cost = 0;
    while (true)