必会算法好题之猴子吃香蕉问题
先上飞机票~~~~~~~~二分好题！友情提醒hhhh
题意：
有n只猴子，第i只猴子每过xi小时会连续吃香蕉yi小时。猴子从第二次开始每次休息结束后这只猴子连续吃香蕉的时间会增加zi小时。给定n只猴子，每一只的xi，yi，zi，以及时间t，求在前t小时中，所有猴子共吃了多少小时。对于一只猴子来说是这样的：
从第1小时开始：
休息xi小时( 1 -> xi )
吃yi小时( xi + 1 -> xi + yi )
休息xi小时
吃yi+zi小时
休息xi小时
吃yi+zi+zi小时
......
思路：
不难想到可以二分，求每个猴子吃香蕉的区间由y和x和z三部分组成，于是可以直接枚举猴子吃香蕉的次数算出来每段区间，这里用个等差数列求和，然后判断完了之后，因为猴子是先休息再吃，那么就有可能还会剩下一点时间，虽然不够t，但是还是可以继续吃的，所以要不一个和t的差值。
要是听不懂再简单点来说就是：
二分一下次数，然后用简单数学推导一下就知道这个猴子吃了多久了
注意的事项：
二分的时候两个2e9加起来会爆掉int的如果二分上界设成2e9，那么中间运算有可能爆炸
发现如果这个猴子吃的时间会增长，那么二分的上界是O( sqrt( t ) )级别的
于是特判这里就可以了~
注意的事项：
二分的时候两个2e9加起来会爆掉int的如果二分上界设成2e9，那么中间运算有可能爆炸
发现如果这个猴子吃的时间会增长，那么二分的上界是O( sqrt( t ) )级别的
于是特判这里就可以了~
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
#define int long long
struct node {
int x,y,z;
}mo[maxn];
int n,t;
bool check(int x,int y,int z,int mid)
{
long long x1=mid*(x+y)+(((mid)*(mid-1))/2)*z;
if(x1<0||x1>t) return false;
return true;
}
signed main()
{
int i;
cin>>n>>t;
for(i=0;i<n;i++)
{
cin>>mo[i].x>>mo[i].y>>mo[i].z;
}
long long ans1=0;
for(i=0;i<n;i++)
{
int l=0,r=2000000005;
while(l<r)
{
int mid=l+r+1ll>>1ll;
if(check(mo[i].x,mo[i].y,mo[i].z,mid))
{
l=mid;
}
else
{
r=mid-1;
}
}
ans1+=l*(mo[i].y)+(l*(l-1))/2*mo[i].z;
if((t-l*(mo[i].y)-((l*(l-1))/2)*mo[i].z-(l+1)*mo[i].x)>0)
{
ans1+=(t-l*(mo[i].y)-((l*(l-1))/2)*mo[i].z-(l+1)*mo[i].x);
}
}
cout<<ans1<<endl;
return 0;
}
牛客公司氛围 176人发布
投递美团等公司10个岗位