wordpress学校网站模板,wordpress 去掉左上角,wordpress批量上传插件下载,品牌建设成果题目描述
小e要把 n n n 本规格相同的书放进书架里#xff0c;对于每一本书#xff0c;他可以横着放也可以竖着放#xff08;不能斜着放#xff09;。
书的宽度为 1 1 1#xff0c;高度为 h h h#xff0c;书架的高度为 t t t#xff0c;意味着如果你横着放#…题目描述
小e要把 n n n 本规格相同的书放进书架里对于每一本书他可以横着放也可以竖着放不能斜着放。
书的宽度为 1 1 1高度为 h h h书架的高度为 t t t意味着如果你横着放每 h h h 长度的书架最多叠 t t t 本如果竖着放每 1 1 1 长度的书架可以放一本书竖着放不能叠起来且书的高度要小于等于书架高度。
注意你不能在横着放的书上面再竖着放也不能在竖着放的书上方横着放书。
请问书架的至少要多长才能放下所有的书
输入格式
第一行一个整数 T T T 表示测试样例个数满足条件 1 ≤ T ≤ 1 0 5 1 ≤ T ≤ 10^5 1≤T≤105。
对于每个样例一行三个整数表示 n n n, h h h, t t t满足条件 1 ≤ n , h , t ≤ 1 0 7 1 ≤ n, h, t ≤ 10^7 1≤n,h,t≤107。
输出格式
对于每个样例在一行输出结果书架的最小长度后换行。
样例
输入样例1
2
6 4 5
4 3 2输出样例1
5
6样例解释
第一个样例前面 5 5 5 本书横着叠放长度为 4 4 4最后一本书竖着放总长度为 5 5 5。
第二个样例书不能竖着放必须全部横着放总长度为 6 6 6。 思路
在主函数中首先读取测试用例的数量。对于每个测试用例再读取三个整数分别代表书的数量书的高度以及书架的高度。
接着初始化了两个变量代表二分查找的左右边界。在进行二分查找的过程中目标是找到一个长度使得check(mid)函数返回true且这个长度尽可能小。
check(mid)函数的作用是检查给定的长度是否满足条件。首先计算如果书横放在书架上最多可以放多少本书。然后如果书架的高度小于等于横放书的数量还会尝试纵放一些书。最后函数返回的是这个总数是否大于等于书的数量即是否有足够的空间来放下所有的书。
在主函数的二分查找过程中每次迭代都会计算中点然后使用check(mid)函数来检查这个中点是否满足条件。如果满足条件那么就将右边界移动到这个中点因为要找到的是满足条件的最小的值否则将左边界移动到这个中点。这个过程会一直重复直到左边界和右边界之间没有其他的值为止。
最后输出满足条件的最小值也就是右边界的值这就是满足条件的最小书架长度。 AC代码
#include iostream
#define ll long long
#define AUTHOR HEX9CF
using namespace std;int m;
int n, h, t;bool check(ll mid) {// 横放ll cnt (mid / h) * t;if (h t) {// 竖放cnt mid % h;}return cnt n;
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin m;for (int i 1; i m; i) {cin n h t;ll l 0;ll r 1e16;while (l 1 r) {ll mid (l r) 1;if (check(mid)) {r mid;} else {l mid;}}cout r endl;}return 0;
}
