BZOJ 5106 [CodePlus2017] 汀博尔

题目链接：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 即可。

#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);
}

#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);

}

zgz233

zgz233

BZOJ 5106 [CodePlus2017] 汀博尔

l1ll5

Comments | NOTHING