题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=5106
题意：
有 n 棵树，初始时每棵树的高度为 Hi，第 i 棵树每月都会长高 Ai。现在有个木料长度总量为 S 的订单，客户要求每块
木料的长度不能小于 L，而且木料必须是整棵树（即不能为树的一部分）。现在问你最少需要等多少个月才能满足
订单。
显然答案具有二分性，所以可以二分答案。
不过二分的上界不能太大，否则会爆 long long，考虑一下发现统计答案的时候每一项是\(mid*a_i+h_i\)，所以记 mx 为最大的\(a_i\)，上界为\(\frac{S}{mx}+1\) 即可。
结果 WA 了，本机测一下发现有 85pts，wa 在了没有考虑 L 很大 S 很小的情况，默认了 S 远大于 L，所以上界在\(\frac{L}{mx}+1\) 和\(\frac{S}{mx}+1\) 间取个 max 即可。
|
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 200010 #define ll long long using namespace std; char xB[1<<15],*xS=xB,*xT=xB; #define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++) inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; ll S,L; struct zgz { ll h,a; }b[N]; bool cmp(const zgz &a,const zgz &b) {return a.a<b.a;} ll mx; bool ck(ll x) { ll now=0; for(int i=1;i<=n;i++) { if(b[i].h+b[i].a*x>=L) now+=b[i].h+b[i].a*x; if(now>=S)return 1; } return 0; } int main() { n=read(),S=read(),L=read();register int i; for(i=1;i<=n;++i)b[i].h=read(); for(i=1;i<=n;++i)b[i].a=read(),mx=max(mx,b[i].a); sort(b+1,b+n+1,cmp); ll l=0,r=max(S/mx,L/mx)+1,ans=0; while(l<=r) { ll mid=(l+r)>>1; if(ck(mid))ans=mid,r=mid-1; else l=mid+1; } printf("%lld\n",ans); } |
Comments | NOTHING