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

第一题

题目：手机流畅运行的秘密

8月份发布会一结束，米小兔就在公司领到了一台最新发布的Xiaomi MIX Fold 3手机，这是一款小米旗舰折叠屏手机，并搭载了全新升级架构的MIU114系统。其先进的应用引擎不仅让系统更流畅，应用体验也大幅提升。在一个优化项中，为了尽可能提升用户白天使用手机的体验和续航，某些已经在系统中注册过的任务会被设置为空闲任务，仅在手机空闲时运行 (比如数据备份或AI相册整理)。现在系统中注册了若干组空闲任务，每个任务有各自的耗电量以及允许任务运行的最低初始电量，我们需要计算手机能够串行完成全部任务的最低初始电量。

注意点1: 所有电量以mAh(毫安时)计，Xiaomi MIX Fold 3的大电池容量是4800mAh。

注意点2:本题目假设手机在运行空闲任务期间，不处于充电状态，也没有额外耗电行为。

注意点3:智能应用引擎会以最合适的顺序串行运行任务。

输入描述

一个描述了所有任务的长字符串。任务与任务之间用逗号阳开，每组任务由耗电量及最低初始电量组成，用冒号限开。

输出描述

一个数字，代表依次完成全部任务的最低初始电量，如果最低初始电量超过手机电池容量，则返回-1。

样例输入

1:10,2:12,3:10

样例输出

13

提示：在样例中，手机至少需要有13mah的初始电量，在运行任务2后剩余电量11mAh、运行任务1后剩余电量10mah、运行任务3后剩余7mah。

参考题解

二分查找

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

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long;

int main () {
    string input; cin >> input;
    int n = input.size();
    vector<vector<ll>> intervals;

    for (int i = 0; i < n; ++i) {
        int j = i;
        while (j < n && input[j] != ',') ++j;
        string intervalStr = input.substr(i, j - i);
        int colonPos = intervalStr.find(':');
        intervals.push_back({stoll(intervalStr.substr(0, colonPos)), stoll(intervalStr.substr(colonPos + 1))});
        i = j;
    }

    sort(intervals.begin(), intervals.end(), [](vector<ll>& a, vector<ll>& b){
        // Choosing 'a' first
        ll timeWithA = a[1] + max(0LL, b[1] - a[1] + a[0]);
        // Choosing 'b' first
        ll timeWithB = b[1] + max(0LL, a[1] - b[1] + b[0]);
        return timeWithA < timeWithB;
    });

    int numIntervals = intervals.size();
    ll totalTime = intervals[0][1];
    ll remainingTime = intervals[0][1] - intervals[0][0];
    ll MAX_TIME = 4800;

    for (int i = 1; i < numIntervals; ++i) {
        if (remainingTime >= intervals[i][1]) {
            remainingTime -= intervals[i][0];
        } else {
            totalTime += intervals[i][1] - remainingTime;
            remainingTime = intervals[i][1] - intervals[i][0];
        }
    }

    if (totalTime > MAX_TIME) {
        cout << -1;
    } else {
        cout << totalTime;
    }
}

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

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int n = s.length();
        List<List<Long>> a = new ArrayList<>();

        for (int i = 0; i < n; ++i) {
            int j = i;
            while (j < n && s.charAt(j) != ',') ++j;
            String ss = s.substring(i, j);
            int p = ss.indexOf(':');
            a.add(List.of(Long.parseLong(ss.substring(0, p)), Long.parseLong(ss.substring(p + 1))));
            i = j;
        }

        Collections.sort(a, (b, c) -> {
            long f1 = b.get(1) + Math.max(0L, c.get(1) - b.get(1) + b.get(0));
            long f2 = c.get(1) + Math.max(0L, b.get(1) - c.get(1) + c.get(0));
            return Long.compare(f1, f2);
        });

        int m = a.size();
        long sum = a.get(0).get(1);
        long r = a.get(0).get(1) - a.get(0).get(0);
        long MAX = 4800;

        for (int i = 1; i < m; ++i) {
            if (r >= a.get(i).get(1)) {
                r -= a.get(i).get(0