newcoder猴子吃香蕉
题目描述
有n只猴子，第i只猴子每过xi小时会连续吃香蕉yi小时。猴子从第二次开始每次休息结束后这只猴子连续吃香蕉的时间会增加zi小时。
给定 n只猴子，每一只的 xi， yi， zi，以及时间 t，求在前 t小时中，所有猴子共吃了多少小时。 对于一只猴子来说是这样的：从第1小时开始：
休息x i小时( 1 -> x i )
吃y i小时( x i + 1 -> x i + y i )
休息x i小时
吃y i+z i小时
休息x i小时
吃y i+z i+z i小时
.... 假设一个猴子吃了Ｋ阶段，Ｋ个阶段就是(x+y) + (x+y+z) + (x+y+z*2) + (x+y+z*3).... 所以二分ｋ的上限．然后再处理一下剩下的时间，注意ｚ的值为０的情况，还有二分的上限不能过大．
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int n;
ll t;
ll x[maxn],y[maxn],z[maxn];
inline bool check(ll mid,int k)
{//printf("%lld %lld\n",mid,mid*(x[k]+y[k]) + mid*(mid-1)/2*z[k]);return mid*(x[k]+y[k]) + mid*(mid-1)/2*z[k]<=t;
}
int main()
{scanf("%d%lld",&n,&t);for(ll i=0;i0)sum += t%(x[i]+y[i])-x[i];continue;}ll l = 0,r = 1e5,mid,ans;while(l<=r){mid = (l+r)/2;int flag = check(mid,i);if(flag) l = mid+1,ans = mid;else r = mid-1;}sum += ans*y[i] + ans*(ans-1)/2*z[i];ll tmp = t-ans*(x[i]+y[i]) - ans*(ans-1)/2*z[i];tmp -= x[i];if(tmp>0&&y[i]&&z[i]){sum += tmp;}else if(tmp>0&&!y[i]&&z[i]){sum += tmp;}}printf("%lld\n",sum);return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！