网易笔试网易笔试题 0817

笔试时间：2024年08月17日比较难，只有前两题有解；

历史笔试传送门：2023秋招笔试合集

第一题

题目：服务器压力之横屿荡寇

横屿荡寇是倩女幽魂手游在23年上线的全新帮会团本。活动开放时间是周日全天，每个帮会有一次开启横屿荡寇副本的机会。为了召集更多帮会成员参与副本，每个帮会往往会在一个约定好的时间点开启副本，以保证帮会成员的参与率。对于不同水平的帮会，通关副本的时间会有所不同。

团本开启期间，服务器负载会随着参与战斗的人数上升而增高。因而负责该玩法的服务器程序小倩想根据历史统计数据，估算周日当天，每组服务器中，最多有多少玩家同时在横屿荡寇副本中战斗。

p.s.一组服务器中的帮会开启副本时，共同使用一份服务器资源，不同组服务器之间互不影响。

输入描述

一行一个数字 M，代表有 M 组不同的服务器需要估算，1<=M<=5。

接着M组数据，每组数据分别为：

一行一个数字 N，代表该服务器有N个帮会，5 <= N <= 20。

N行数据，每一行数据表示该帮会信息，格式如下：

hh:mm k t

分别表示：

hh:mm开启副本的时间,例如09:20、16:04，输入保证时间格式正确。

k参与副本的人数，为正整数，范围 10 <= k <= 100

t副本持续时长，单位为分钟，范围 30 <= t <= 120。

p.s.副本开启时即开始计算持续时长，例如 15:40 开启，持续60分钟，意味着 15:40 到16:39 期间，该帮会在副本内战斗。16:40时，该帮会已经离开副本，不再计入统计。

p.p.s.数据保证副本一定在今日完成。

输出描述

对于每组服务器，输出当日该服务器最多有多少人同时参与横屿荡寇副本。

样例输入

3

5

16:00 30 90

17:00 15 120

16:20 28 80

10:05 30 120

09:02 50 70

5

16:00 30 90

17:29 15 120

16:20 28 80

10:05 20 120

09:02 10 70

5

16:00 30 90

17:30 15 120

16:20 28 80

10:05 20 120

09:02 10 70

样例输出

80

73

58

说明

第一组服务器，10:05-10:11期间有80人同时在进行横屿荡寇副本，人数最多。

第二组服务器，17:29时有73人同时在进行横屿荡寇副本，人数最多。

第三组服务器，16:20-17:29期间有58人，17:30-17:39期间有43人，故输出58。

参考题解

我们可以将每个帮会的副本开启时间和结束时间视作一个事件。具体来说，每个帮会的副本开启时，其参与人数会对并发人数产生正影响（人数增加），而副本结束时，其参与人数会对并发人数产生负影响（人数减少）。因此，可以将副本的开始和结束时间分别视为两个时间点事件，在这些事件上分别加上或减去该帮会的参与人数。差分法的关键是通过记录这些时间点的变化来累加计算出在每个时刻的最大并发人数。

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

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 转换为以分钟为单位
int parse(const string& time_str) {
    int hh = stoi(time_str.substr(0, 2));
    int mm = stoi(time_str.substr(3, 2));
    return hh * 60 + mm;
}


int solve(const vector<tuple<string, int, int>>& server_data) {
    map<int, int> time_changes;

    for (const auto& [start_time, players, duration] : server_data) {
        int start_minutes = parse(start_time);
        int end_minutes = start_minutes + duration;


        time_changes[start_minutes] += players;


        time_changes[end_minutes] -= players;
    }

    int max_players = 0;
    int current_players = 0;
    for (const auto& [time_point, change] : time_changes) {
        current_players += change;
        max_players = max(max_players, current_players);
    }

    return max_players;
}

int main() {
    int M; 
    cin >> M;

    while (M--) {
        int N; 
        cin >> N;

        vector<tuple<string, int, int>> server_data;

        for (int i = 0; i < N; ++i) {
            string hhmm;
            int k, t;
            cin >> hhmm >> k >> t;
            server_data.emplace_back(hhmm, k, t);
        }

        cout << solve(server_data) << endl;
    }

    return 0;
}

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

import java.util.*;

public class Main {

    // 转换为以分钟为单位
    public static int parse(String timeStr) {
        int hh = Integer.parseInt(timeStr.substring(0, 2));
        int mm = Integer.parseInt(timeStr.substring(3, 5));
        return hh * 60 + mm;
    }

    public static int solve(List<ServerData> serverDataList) {
        TreeMap<Integer, Integer> timeChanges = new TreeMap<>();

        for (ServerData data : serverDataList) {
            int startMinutes = parse(data.startTime);
            int endMinutes = startMinutes + data.duration;

            timeChanges.put(startMinutes, timeChanges.getOrDefault(startMinutes, 0) + data.players);
            timeChanges.put(endMinutes, timeChanges.getOrDefault(endMinutes, 0) - data.players);
        }

        int maxPlayers = 0;
        int currentPlayers = 0;

        for (int change : timeChanges.values()) {
            currentPlayers += change;
            maxPlayers = Math.max(maxPlayers, currentPlayers);
        }

        return maxPlayers;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();

        while (M-- > 0) {
            int N = scanner.nextInt();
            List<ServerData> serverDataList = new ArrayList<>();

            for (int i = 0; i < N; ++i) {
                String hhmm = scanner.next();
                int k = scanner.nextInt();
                int t = scanner.nextInt();
                serverDataList.add(new ServerData(hhmm, k, t));
            }

            System.out.println(solve(serverDataList));
        }

        scanner.close();
    }
}

class ServerData {
    String startTime;
    int players;
    int duration;

    public ServerData(String startTime, int players, int duration) {
        this.startTime = startTime;
        this.players = players;
        this.duration = duration;
    }
}

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

def parse(time_str):
    hh, mm = map(int, time_str.split(':'))
    return hh * 60 + mm

def solve(server_data):
    time_changes = {}

    for start_time, players, duration in server_data:
        start_minutes = parse(start_time)
        end_minutes = start_minutes + duration


        if start_minutes in time_changes:
            time_changes[start_minutes] += players
        else:
            time_changes[start_minutes] = players


        if end_minutes in time_changes:
            time_changes[end_minutes] -= players
        else:
            time_changes[end_minutes] = -players


    max_players = 0
    current_players = 0
    for time_point in sorted(time_changes):
        current_players += time_changes[time_point]
        max_players = max(max_players, current_players)

    return max_players


M = int(input()) 

for _ in range(M):
    N = int(input()) 
    server_data = []

    for _ in range(N):
        hhmm, k, t = input().split()
        k = int(k)
        t = int(t)
        server_data.append((hhmm, k, t))


    print(solve(server_data))

第二题

题目：师门整顿

在逆水寒手游师徒系统里，一个师傅最多能有五个徒弟，一个徒弟只能有一个师傅（测试用例会保证这个数据的正确性）。每个玩家只能与一位其他玩家绑定情缘关系。参考近亲不可结婚的原则（非完全一样），游戏对于情缘关系也有限制，师门规则是：同一师门中关系中，相隔小于三代之内不可建立情缘关系。现在给出两组包含师徒关系以及情缘关系数据的玩家id数组，需要你找出其中违反师门规则的所有玩家id。