笔试时间：2025年8月2日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：排队

某个银行只有一个营业员,只能同时办理一个人的业务。因为营业员人数有限,所以除了首个办理业务的人之外,其他所有人都需要等待前一个办理业务的人办理完成。

假设现在有n个人需要办理业务,第i个人的业务需要办理a[i]分钟。

由于业务的特殊性,第i个人每等1分钟,他最终办理业务的时间就会多b[i]分钟。

作为志愿者,你的任务就是安排他们的先后顺序,使每个人办理业务的总时间(包括等待时间)之和最小。

输入描述

第一行一个数n,表示有n个人(1<=n<=10000)。

接下来n行,每行两个数a[i],bi。

输出描述

一行一个整数,输出最小时间。如果答案过大,需要对10000000009取模(求余)。

样例输入

2

1 1

2 5

样例输出

5

提示：若第1个人先办理业务,然后第2个人办理业务: 第1个人办理业务的时间是1分钟 第2个人办理业务的时间是2+15=7分钟 总时间之和为8分钟 若第2个人先办理业务,然后第1个人办理业务: 第2个人办理业务的时间是2分钟 第1个人办理业务的时间是1+21=3分钟 总时间之和为5分钟 所以最小时间是5分钟。

参考题解

每个人的业务办理时间包括基础时间a[i]和等待时间乘以系数b[i]（即每等待1分钟，业务时间增加b[i]分钟）。最优的排序策略是按照a[i]/b[i]的比值从小到大排序，这样可以最小化总时间。计算总时间时，我们模拟每个人的办理过程，累加每个人的实际时间，并更新等待时间总和。通过贪心策略，将a[i]/b[i]比值最小的人排在前面。这等价于比较a[i]*b[j]和a[j]*b[i]：若a[i]*b[j] < a[j]*b[i]，则i应排在j前面。按排序顺序处理每个人，计算每个人的实际时间T = a[i] + 当前等待时间总和 * b[i]。累加每个人的实际时间得到总时间，并更新等待时间总和。

C++：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod = 1000000009;

struct Pair {
    ll a, b;
};

bool cmp(const Pair &x, const Pair &y) {
    return x.a * y.b < y.a * x.b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Pair> arr(n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i].a >> arr[i].b;
    }

    sort(arr.begin(), arr.end(), cmp);

    ll total_time = 0;
    ll current_sum = 0;

    for (auto &p : arr) {
        ll T = (p.a + current_sum * p.b) % mod;
        total_time = (total_time + T) % mod;
        current_sum = (current_sum + T) % mod;
    }

    cout << total_time << "\n";
    return 0;
}

Java：

import java.util.*;

public class Main {
    static final long mod = 1000000009L;

    static class Pair {
        long a, b;
        Pair(long a, long b) {
            this.a = a;
            this.b = b;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Pair> arr = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            arr.add(new Pair(a, b));
        }

        arr.sort((x, y) -> {
            long cmp = x.a * y.b - y.a * x.b;
            if (cmp < 0) return -1;
            else if (cmp > 0) return 1;
            return 0;
        });

        long total_time = 0;
        long current_sum = 0;

        for (Pair p : arr) {
            long T = (p.a + current_sum * p.b) % mod;
            total_time = (total_time + T) % mod;
            current_sum = (current_sum + T) % mod;
        }

        System.out.println(total_time);
    }
}

Python：

import functools

mod = 1000000009
n = int(input())
arr = []
for _ in range(n):
    a, b = map(int, input().split())
    arr.append((a, b))

def cmp(x, y):
    a1, b1 = x
    a2, b2 = y
    if a1 * b2 < a2 * b1:
        return -1
    elif a1 * b2 >