题解

题面描述

$Gerry$ 的店里有 $n$ 个顾客使用兑换券兑换 $m$ 个糖果，每张糖果兑换券可以兑换 $k$ 个糖果。但实际上，单次兑换中所需要的兑换券数 $y$ 与获得的糖果数 $x$ 满足下列类似于四舍五入的关系：

也就是说，对于一次兑换，如果顾客使用 $y$ 张兑换券，则 $x$ 必须落在

的区间内。每个顾客最多只能进行一次兑换，而所有 $m$ 个糖果必须全部兑换完。问题要求求出在满足条件下最少需要多少张兑换券。

思路

由于每张兑换券原则上可以兑换 $k$ 个糖果，但实际兑换时由于“四舍五入”的规则，顾客在一次交易中可以“凑出”比 $y\cdot k$ 更多的糖果。例如，对于一次用 $y$ 张券的交易，按照不超过上界的要求，

$\frac{x}{k}$ < $y$ + $0.5$ $\quad \Longrightarrow \quad x$ $\le k\Bigl(y + 0.5\Bigr)-1.$

同时下界要求

$\frac{x}{k} \ge$ $y$ - $0.5 \quad \Longrightarrow \quad$$x\ge k\Bigl(y-0.5\Bigr)$$\quad (\text{考虑到} \, x \, \text{非负}).$

为达到最小使用券数的目标，在不改变券数的条件下，我们希望每次交易“产出”尽可能多糖果。换句话说，对于给定的 $y$，一次交易最多可以得到

• 当 $k$ 为偶数时，由于 $k\cdot0.5=\frac{k}{2}$ 为整数，所以$$x_{\max} = y\cdot k + \frac{k}{2} - 1.$$
• 当 $k$ 为奇数时，$k\cdot0.5$ 不是整数，取整后$$x_{\max} = y\cdot k + \frac{k-1}{2}.$$

注意：当 $y=0$ 时，交易允许兑换的糖果范围是

因此最多能兑换到：

• $x_{\max} = \frac{k}{2} - 1$（若 $k$ 为偶数）；
• 或 $x_{\max} = \frac{k-1}{2}$（若 $k$ 为奇数）。

当一次交易使用 $y$ 张券时，最多兑换糖果数为

又因为最多 $n$ 个顾客（交易）可用，为使 $m$ 个糖果全部兑换完，我们可以利用最多 $n$ 次交易，各自独立选取适合的 $y$ 值，其总代价（券数总和）为 $X=\sum_{i=1}^{n} y_i$。为了达到最大化总兑换糖果数（上界），最佳方案显然是所有交易均取最大值（即让每顾客的交易达到上界），这时总糖果数上界为

为了满足兑换完 $m$ 个糖果，我们必须有

显然，当 $n\cdot C \ge m$ 时，全部交易均用 $0$ 张券即可；否则，我们所需额外的券数至少为

因此问题的答案为

C++ 代码

#include <iostream>
#include <cmath>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 输入组数T
    int T;
    cin >> T;
    while(T--){
        // 输入n, m, k
        long long n, m, k;
        cin >> n >> m >> k;
        
        // 根据k的奇偶性计算基础兑换量C
        long long C;
        if(k % 2 == 0)
            C = k / 2 - 1;    
        else
            C = (k - 1) / 2;  
        
        // 判断若所有顾客均用0张券时是否能兑换完m个糖果
        if(n * C >= m){
            cout << 0 << "\n";
        } else {
            
            long long need = m - n * C;
            long long ans = (need + k - 1) / k; 
            cout << ans << "\n";
        }
    }
    return 0;
}

Python 代码

import math

def main():
    import sys
    input = sys.stdin.readline
    # 读取组数T
    T = int(input().strip())
    for _ in range(T):
        # 读取n, m, k
        n, m, k = map(int, input().split())
        # 根据k的奇偶性计算基础兑换量C
        if k % 2 == 0:
            C = k // 2 - 1  
        else:
            C = (k - 1) // 2  
        
        # 判断若所有顾客均用0张券时是否能兑换完m个糖果
        if n * C >= m:
            print(0)
        else:
            
            need = m - n * C
          
            ans = (need + k - 1) // k
            print(ans)

if __name__ == '__main__':
    main()

Java 代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        // 使用 BufferedReader 读取输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int T = Integer.parseInt(br.readLine().trim()); // 读取组数T
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long n = Long.parseLong(st.nextToken()); // 读取n
            long m = Long.parseLong(st.nextToken()); // 读取m
            long k = Long.parseLong(st.nextToken()); // 读取k
            
            // 根据k的奇偶性计算基础兑换量C
            long C;
            if(k % 2 == 0) {
                C = k / 2 - 1; 
            } else {
                C = (k - 1) / 2; 
            }
            
            // 判断若所有顾客均用0张券时是否能兑换完m个糖果
            if(n * C >= m) {
                out.println(0);
            } else {
                long need = m - n * C;
                long ans = (need + k - 1) / k; 
                out.println(ans);
            }
        }
        out.flush();
        out.close();
    }
}

题目内容

$Gerry$的店里有$n$个顾客使用兑换券兑换$m$个糖果，每张糖果兑换券可以兑换$k$个糖果。单次兑换所需的兑换券数$y$与糖果数$x$有如下关系，类似于四舍五入。

$mod$表示取模运算

$Gerry$有如下要求

• 每个客户最多交易$1$次
• $m$个糖果需要全部兑换完

$Gerry$想知道要兑换完所有的糖果，至少需要多少张兑换券，请帮忙计算一下。

输入描述

第一行一个数字$T(1≤T≤1000)$

接下来$T$行，每行三个数字:

$n,m,k;(1≤n≤10^9,$$1≤m≤10^{18},2 ≤k≤10^9)$

对于每组数据输入$n、m、k$分别表示顾客数量、糖果数量和每张兑换券兑换多少糖果。

输出描述

输出$T$行，每行表示最少需要多少兑换券。

样例1

输入

2
3 300 100
2 100 160

输出

3
0