问题描述
经营一家糖果店是非常困难的，你需要优化各种各样的东西。最近你在销售一种非常时髦的糖果，叫做Whizboppers。这种糖果变质非常迅速，所以：
·你必须每天早上从供应商买来新的Whizboppers。
·你必须用当天早上从供应商买来的盒子装着糖果出售。
你可以从你的供应商处买来装有任意整数克糖果的盒子。
每天有至多k位顾客到你的店里来。从第1个人开始，每个人会选择花费整数分的钱来买Whizboppers，钱数在1分到C分之间（包含1分和C分）。你打算以1分钱每克的价格出售；所以如果一个人想要花4分钱，你会给他恰好4克糖果。你可以给他1个4克的盒子，也可能是1个2克的盒子和2个1克的盒子。
你最少需要买几个盒子才能保证，不管每个人想花多少钱买糖，你总是可以给他们对应质量的糖果？
注意：当一个人选择自己想买多少糖果后，你知道之前的人已经买了多少糖，但不能预知之后的人打算买多少糖。
举个例子，如果每天至多有2位顾客到你的店里，每个人至多花2分钱(k=2,C=2)，你可以从你的供应商买4个1克的盒子。但是你可以做的更好：只要买2个1克的盒子和1个2克的盒子，就可以满足你的顾客。如下所示：
第一个人给第一个人的盒子第二个人给第二个人的盒子2分1 个 2克2分
1分2 个 1克
1 个 1克1分1 个 1克2分
1分1 个 2克
1 个 1克
不论第一个人怎么买，你都可以给他对应质量的盒子，同时保证第二个人也能拿到正确质量的糖果。所以对于k=2,C=2，你用3个盒子就可以满足任意的顾客需求。
输入格式
第一行一个整数T，表示询问数量。
接下来T行，每行包含两个整数k和C，分别表示最大人数和每个人花费的最多钱数。
输出格式
对于每一个询问，输出一行包含"Case #x: y"，x是询问编号（从1开始标号），y是你每天最少需要的盒子数量。
帮你梳理一下思路，这个问题有两个关键点：
1、需要的盒子的容量必须大于等于顾客的最大购买量。
2、不论哪种情况，永远从2个1克的盒子开始计算。
例如，样例2 2，即每天至多有2位顾客到你的店里，每个人至多花2分钱，此时：
1）最大购买数量为：2*2=4g
2）先给定两个1克的盒子：1g*2，容量：2g
如果每人购买2g，则总共需要可装4g的盒子，此时的问题是：如何确定下一个盒子？
当然，题目已经告诉我们了还需要1个2g的盒子，那么这个1个如何确定的呢？
确定方法：(4-2)/2=1。
至此，容量为4g，满足最大购买数量，需要3个盒子，规格为：1g*2,2g*1。
当然也有除不尽的情况，方法是向上取整。
例如，样例：1 5，即每天至多有1位顾客到店，至多花费5分钱，此时：
1）最大购买数量为：1*5=5g
2）先给定两个1克的盒子：1g*2，容量：2g
如果这个顾客购买3g，此时的问题是：如何确定下一个盒子？
确定方法：(3-2)/3=0.333，向上取整为1，所以还需要1个3g的盒子。
至此，容量为5g，满足最大购买数量，需要3个盒子，规格为：1g*2,3g*1。
再比如，样例2 50，即每天至多有2位顾客到店，至多花费50分钱，此时：
1）最大购买数量为：2*50=100g
2）先给定两个1克的盒子：1g*2，容量：2g
如果每人购买2g，则还需要1个2g的盒子（前面已给出），此时容量为4g
如果每人购买3g，则总共需要可装6g的盒子，此时的问题依然是：如何确定下一个盒子？
确定方法：(6-4)/3=0.67，向上取整为1，所以还需要1个3g的盒子，此时容量为7g
如果每人购买4g，则需要可装8g的盒子，此时的问题依然是：如何确定下一个盒子？
确定方法：(8-7)/4=0.25，向上取整为1，所以还需要1个4g的盒子，此时容量为11g
如果每人购买6g，则需要可装12g的盒子，此时的问题依然是：如何确定下一个盒子？
确定方法：(12-11)/6=1/6，向上取整为1，所以还需要1个6g的盒子，此时容量为17g
为什么是：如果每人购买6g？因为每次“如果”，都要使需要的容量超过了前一次的容量。
......
以此类推，直到容量大于等于100g，最终发现需要的盒子数量是11个，规格为：1g*2,2g*1,3g*1,4g*1,6g*1,......
这就是这个问题的基本思路。
代码可以参考：
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int n, k, count = 1;
long long c;
cin >> n;
while (n--)
{
cin >> k >> c;
int num = k;
long long sum = k;
for (long long i = 2; i <= c; i = sum / k + 1)
{
int t = num;
num += ceil((k * i - sum) * 1.0 / i);
sum += i * (num - t);
}
cout << "Case #" << count++ <<": " << num << endl;
}
return 0;
}
您好，我是有问必答小助手，您的问题已经有小伙伴解答了，您看下是否解决，可以追评进行沟通哦~
如果有您比较满意的答案 / 帮您提供解决思路的答案，可以点击【采纳】按钮，给回答的小伙伴一些鼓励哦～～
ps:问答VIP仅需29元，即可享受5次/月 有问必答服务，了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632
非常感谢您使用有问必答服务，为了后续更快速的帮您解决问题，现诚邀您参与有问必答体验反馈。您的建议将会运用到我们的产品优化中，希望能得到您的支持与协助！
速戳参与调研>>>https://t.csdnimg.cn/Kf0y