题面描述

• 问题：有$n$个人，第$i$个人的基础办理时长为$a[i]$。由于业务特殊性，若他在开始办理前等待了$W$分钟，则其实际办理时长变为$a[i] + b[i]*W$。银行只有一个窗口，同一时刻只能服务一人。请安排办理顺序，使所有人的实际办理时长之和最小，并输出最小值对 $1000000009$ 取模。
• 输入：第一行$n$（$1 \le n \le 10000$），接下来$n$行每行$a[i], b[i]$（$1 \le a[i], b[i] \le 10000$）。
• 输出：一个整数，为最小总时长对$1000000009$取模。

思路

• 关键化简：总的实际办理时长之和等于整个队伍的结束时间（最后一人的结束时刻），记为 $D_n$。若当前累积时间为$C$，处理第$i$个人之后变为

  $$C' = a_i + (1 + b_i)\cdot C$$

  即每个人对应一个仿射函数$g_i(x) = a_i + (1+b_i)\cdot x$。总时间即为$g_{pi(n)} \cdots g_{pi(1)}(0)$。

• 交换论证：考虑相邻两人$i$ 与$j$，在某个前缀累积时间为$X$ 下：

  $$g_j(g_i(X)) - g_i(g_j(X)) = a_i b_j - a_j b_i$$

  与 $X$ 无关。因此，当且仅当 $a_i b_j > a_j b_i$ 时，交换为$j,i$更优。

• 排序规则：将人员按比值$a_i / b_i$ 升序排序（用交叉乘避免除法），即可得到最优顺序。

• 递推求值：按该顺序从前到后递推

  

  最终$\text{cur}$ 即为答案。

C++

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

static const long long MOD = 1000000009LL;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	if (!(cin >> n)) return 0;
	struct Node { long long a, b; };
	vector<Node> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i].a >> v[i].b;
	}
	// 按 a/b 升序排序（用交叉乘比较，避免浮点）
	stable_sort(v.begin(), v.end(), [](const Node& x, const Node& y){
		// x.a/x.b < y.a/y.b  <=>  x.a * y.b < y.a * x.b
		long long lhs = x.a * y.b;
		long long rhs = y.a * x.b;
		if (lhs != rhs) return lhs < rhs;
		// 比值相同任意，做个稳定细分（非必要）
		return x.b < y.b;
	});
	// 递推 cur = a + (1+b)*cur
	long long cur = 0;
	for (auto &it : v) {
		long long term = ( ( (1 + it.b) % MOD ) * cur ) % MOD;
		cur = (term + (it.a % MOD)) % MOD;
	}
	cout << (cur % MOD + MOD) % MOD << "\n";
	return 0;
}

Python

import sys

MOD = 1000000009

def main():
	data = sys.stdin.read().strip().split()
	if not data:
		return
	it = iter(data)
	n = int(next(it))
	arr = []
	for _ in range(n):
		a = int(next(it)); b = int(next(it))
		arr.append((a, b))
	# 按 a/b 升序，用交叉乘法比较
	arr.sort(key=lambda x: (x[0] / x[1], x[1]))  # 简便写法，但有浮点
	# 为避免浮点，可改为自定义比较器；此处用装饰器法实现稳定性
	# 如果担心浮点，可使用下面注释的排序方式（需要 Python3.10+ 可用 functools.cmp_to_key）:
	# from functools import cmp_to_key
	# def cmp(p, q):
	# 	a1, b1 = p; a2, b2 = q
	# 	val = a1 * b2 - a2 * b1
	# 	if val < 0: return -1
	# 	if val > 0: return 1
	# 	return (b1 > b2) - (b1 < b2)
	# arr.sort(key=cmp_to_key(cmp))

	cur = 0
	for a, b in arr:
		cur = ( ( (1 + b) % MOD ) * cur + a ) % MOD
	print(cur % MOD)

if __name__ == "__main__":
	main()

Java

import java.io.*;
import java.util.*;

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

	static class FastScanner {
		BufferedInputStream in = new BufferedInputStream(System.in);
		byte[] buffer = new byte[1 << 16];
		int ptr = 0, len = 0;
		int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		String next() throws IOException {
			StringBuilder sb = new StringBuilder();
			int c;
			while ((c = read()) != -1 && c <= ' ') {}
			if (c == -1) return null;
			do {
				sb.append((char)c);
				c = read();
			} while (c != -1 && c > ' ');
			return sb.toString();
		}
	}

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

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner();
		String s = fs.next();
		if (s == null) return;
		int n = Integer.parseInt(s);
		List<Node> list = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			long a = Long.parseLong(fs.next());
			long b = Long.parseLong(fs.next());
			list.add(new Node(a, b));
		}
		// 按 a/b 升序排序（比较 a1*b2 与 a2*b1）
		list.sort((p, q) -> {
			long lhs = p.a * q.b;
			long rhs = q.a * p.b;
			if (lhs < rhs) return -1;
			if (lhs > rhs) return 1;
			// 比值相同任意，细分一下（非必要）
			return Long.compare(p.b, q.b);
		});
		// 递推 cur = a + (1+b)*cur (取模)
		long cur = 0;
		for (Node nd : list) {
			long term = ((1 + nd.b) % MOD) * (cur % MOD) % MOD;
			cur = (term + (nd.a % MOD)) % MOD;
		}
		System.out.println((cur % MOD + MOD) % MOD);
	}
}

题目内容

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

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

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

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

输入描述

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

接下来$n$行，每行两个数$a[i]，b[i]( 1<= a[i], b[i]<=10000)$。

输出描述

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

样例1

输入

2
1 1
2 5

输出

5

说明

若第$1$个人先办理业务，然后第$2$个人办理业务:

第$1$个人办理业务的时间是$1$分钟

第$2$个人办理业务的时间是$2+1*5=7$分钟

总时间之和为$8$分钟

若第$2$个人先办理业务，然后第$1$个人办理业务:

第$2$个人办理业务的时间是$2$分钟

第$1$个人办理业务的时间是$1+2*1=3$分钟

总时间之和为$5$分钟

所以最小时间是$5$分钟。