[noip2016-普及] 买铅笔

题目描述

P 老师要买至少 $n$ 支铅笔。商店有 $3$ 种整包包装，第 $i$ 种每包 $a_i$ 支、价格 $p_i$ 。只能买同一种包装，不能拆包。求最小花费。

输入格式：第一行 $n$ ；接下来三行每行两个正整数 $a_i, p_i$ 。所有数 $\le 10^4$ 。

输出格式：一个整数，表示最少花费。

样例输入/输出：见 problem.md。

思路

对每种包装，最少份数为 $\lceil n / a_i \rceil$ ，花费为份数乘单价。三种包装取最小值即可。

参考代码

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#!/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 11:56
# update_at: 2026-10-02 11:56

import sys

data = map(int, sys.stdin.read().split())


def cost(n: int, qty: int, price: int) -> int:
    """整包买至少 n 支该包装铅笔的花费：不够一包也要按一整包算。"""
    return (n + qty - 1) // qty * price  # 向上取整的份数 × 单包价格


def solve() -> None:
    n = next(data)
    packs = [(next(data), next(data)) for _ in range(3)]  # 三种包装：(数量, 价格)
    print(min(cost(n, qty, price) for qty, price in packs))


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/**
 * 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 15:31
 * update_at: 2026-10-06 15:31
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

ll n;
ll a[4], p[4]; // 三种包装：a[i] 每包数量，p[i] 每包价格

// 买第 i 种包装至少凑够 n 支的花费：向上取整份数 × 单价
ll cost(ll i) {
    ll k = (n + a[i] - 1) / a[i]; // 最少份数
    return k * p[i];
}

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

    cin >> n;
    for (int i = 1; i <= 3; ++i) cin >> a[i] >> p[i];

    ll ans = cost(1);
    for (int i = 2; i <= 3; ++i)
        ans = min(ans, cost(i));

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

[noip2016-普及] 买铅笔

目录

题目描述

思路

参考代码