牛客练习赛6 A 猴子吃香蕉（等差数列）
题目链接：https://www.nowcoder.com/acm/contest/26/A
题目描述
有n只猴子，第i只猴子每过xi小时会连续吃香蕉yi小时。猴子从第二次开始每次休息结束后这只猴子连续吃香蕉的时间会增加zi小时。
给定n只猴子，每一只的x i，y i，z i，以及时间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小时
......
输入描述:
第一行两个数n和t;
之后n行，第i+1行每行三个数xi,yi,zi.
输出描述:
输入
输出
说明
输入
输出
说明
备注:
解析：如果直接暴力的话，必然会超时，所以肯定有O(n)或者O(n*log(n))的方法，其实仔细一想，这个是一个等差数列，公差d = z[i]， a1 = x[i] + y[i]，an = a1 + (n-1)*d，然后就是求前n项的和Sn = t，这里不知道n，列一个一元二次的方程解除n然后计算时间即可
代码：
#include
using namespace std;typedef long long LL;//d = z
//a1 = x+y
//a2 = a1+d
//
//an = a1 + (n-1)*d
//
//2*t = 2sn = n*(a1+an) = n*(2a1+(n-1)*d)
//ax^2+bx+c=0
//
//2a1*n+d*n^2-dn-2*t = 0
//
//d*n^2 + (2a1-d)n + (-2t) = 0
//
//a = d;
//b = 2a1-d
//c = -2t
//
//x =
//
//
//ans = n*x
//LL x[100009], y[100009], z[100009];int main()
{LL n, t;scanf("%lld%lld", &n, &t);for(int i = 1; i <= n; i++) scanf("%lld%lld%lld", &x[i], &y[i], &z[i]);long long ans = 0, a, b, c, X, cur;for(int i = 1; i <= n; i++){cur = t;if(!z[i]){LL now = 0;now += cur/(x[i]+y[i])*y[i];cur %= (x[i]+y[i]);cur -= x[i];if(cur > 0) now += cur;ans += now;continue;}a = z[i];b = 2ll*(x[i]+y[i])-a;c = -2ll*t;X = (long long)((-b+sqrt(b*b-4.0*a*c))/2.0/a + 1e-8);if(X > 0){LL now = 0;LL k = X*(x[i]+y[i]+x[i]+y[i]+z[i]*(X-1))/2;now += k - X*x[i];cur -= k;cur -= x[i];if(cur > 0) now += cur;ans += now;}}printf("%lld\n", ans);return 0;} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！