史莱姆鱼

题目描述

阿什尼要运 $n$ 条史莱姆鱼回饭店：运第 $i$ 条鱼需要 $2t_i$ 个单位时间（往返），鱼会随时间变重——在时刻 $T$ 开始运第 $i$ 条鱼要消耗 $T\cdot c_i$ 的体力。第一条鱼在时刻 0 开始运送，体力为 0。选择合适的运送顺序，求最少消耗的总体力。

输入：第一行一个整数 $n$ ；接下来 $n$ 行，每行两个整数 $t_i, c_i$ 。输出：一个整数，表示最少消耗的体力。数据范围： $n \leqslant 10^5$ ， $t_i \leqslant 2\times 10^6$ ， $c_i \leqslant 100$ 。

样例输入 6\n3 1 2 5 2 3 3 2 4 1 1 6，样例输出 86。

思路

设相邻两条鱼 $i$ （先）、 $j$ （后），它们之前的鱼共耗时 $T$ ，两条鱼贡献的体力相减得 $(i\text{ 先})-(j\text{ 先})=2(t_ic_j-t_jc_i)$ ，与其余鱼无关；因此若 $t_ic_j>t_jc_i$ （即 $t_i/c_i>t_j/c_j$ ）交换后更优，最优顺序就是按 $t_i/c_i$ 升序。比较用交叉相乘 $t_ic_j$ 与 $t_jc_i$ ，避免浮点误差和 $c_i=0$ 的除零。排序后从时刻 0 顺序扫描：先累加当前开始时刻乘 $c_i$ ，再把时刻推进 $2t_i$ ，答案用 long long（最大约 $4\times10^{18}$ ）。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 19:28
# update_at: 2026-10-02 19:28

import sys
from functools import cmp_to_key


def by_ratio(a: tuple[int, int], b: tuple[int, int]) -> int:
    """按脾气比 t_i/c_i 升序比较：交叉相乘，避免除法和 c_i=0 的除零。"""
    return a[0] * b[1] - b[0] * a[1]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    fish = [(next(data), next(data)) for _ in range(n)]  # 每条鱼 (t_i, c_i)
    fish.sort(key=cmp_to_key(by_ratio))  # 相邻逆序交换只会更优，故按比值排序即最优

    elapsed = 0  # 当前时刻：前面所有鱼往返耗时之和
    cost = 0
    for take, temper in fish:
        cost += elapsed * temper  # 此刻开始运的体力 = 时刻 × 脾气（第一条体力 0）
        elapsed += take * 2       # 运一条鱼要往返，耗时 2*t_i

    print(cost)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 02:17
 * update_at: 2026-10-06 02:17
 */
#include <cstdio>
#include <algorithm>

typedef long long ll;

const int MAXN = 100005;

// 每条鱼的两个参数
struct Fish {
    ll t; // 运送一条鱼需要 2*t 的时间
    ll c; // 脾气系数，开始时刻为 S 时消耗 S*c 体力
};

int n;
Fish fish[MAXN];

// 贪心比较：t_i/c_i 小的排前面，用交叉相乘避免浮点除法和除零
bool cmp_fish(const Fish &a, const Fish &b) {
    return a.t * b.c < b.t * a.c;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lld %lld", &fish[i].t, &fish[i].c);

    // 按 t_i/c_i 升序排序：交换相邻两条可证逆序对必劣
    std::sort(fish + 1, fish + n + 1, cmp_fish);

    // elapsed 是当前鱼的开始时刻；第一条鱼从时刻 0 开始，体力为 0
    ll elapsed = 0;
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += elapsed * fish[i].c; // 记账当前鱼的体力
        elapsed += fish[i].t * 2;   // 推进时刻：往返耗时 2*t
    }
    printf("%lld\n", ans);
    return 0;
}

目录

题目描述

思路

参考代码