P4058 [Code+#1]木材
题目描述
有 \(n\) 棵树,初始时每棵树的高度为 \(H_i\),第 \(i\) 棵树每月都会长高 \(A_i\)。现在有个木料长度总量为 $ S$ 的订单,客户要求每块木料的长度不能小于 \(L\),而且木料必须是整棵树(即不能为树的一部分)。现在问你最少需要等多少个月才能满足订单。
输入格式
第一行 \(3\) 个用空格隔开的非负整数 \(n,S,L\),表示树的数量、订单总量和单块木料长度限制。
第二行 \(n\) 个用空格隔开的非负整数,依次为 \(H_1,H_2, ... ,H_n\)。
第三行 \(n\) 个用空格隔开的非负整数,依次为 \(A_1,A_2, ... ,A_n\)。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1
3 74 51
2 5 2
2 7 9
输出 #1
7
说明/提示
对于样例,在六个月后,各棵树的高度分别为 \(14,47,56\),此时无法完成订单。
在七个月后,各棵树的高度分别为 \(16,54,65\),此时可以砍下第 \(2\) 和第 \(3\) 棵树完成订单了。
来自 CodePlus 2017 11 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/郑林楷 命题/郑林楷 验题/王聿中
Git Repo:https://git.thusaac.org/publish/CodePlus201711
感谢腾讯公司对此次比赛的支持。
【思路】
二分答案!
二分答案模板题
二分最少需要多少个月
然后去检查
枚举每一个树长k个月之后的长度
如果超出ll那就ans加上
如果最后ans大于等于s那么就返回真
否则返回假
重点是r的赋值
可以比较s和ll的最大值然后赋值上去
没必要自己想一个以为可以AC的数赋值上去
除非你疯狂提交二分出可以AC得数qwq
做完这道题之后发现我真是个憨憨
明明可以赋值r为s和ll的最大值
但是我却非要自己试数
(我还真把自己当电脑了真是个憨憨)
【完整代码】
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int Max = 200005;
int h[Max],a[Max];
int n,s,ll;
bool check(int mid)
{
int ans = 0;
for(register int i = 1;i <= n;++ i)
{
int qwq = h[i] + a[i] * mid;
if(qwq < ll)continue;
ans += qwq;
if(ans >= s)return true;
}
return false;
}
signed main()
{
cin >> n >> s >> ll;
for(register int i = 1;i <= n;++ i)
cin >> h[i];
for(register int i = 1;i <= n;++ i)
cin >> a[i];
int l = 0,r = max(s,ll);
while(l < r)
{
int mid = (r + l) >> 1;
if(check(mid))r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}