[二分]煤气灶
链接：https://ac.nowcoder.com/acm/problem/21860
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
小j开始打工，准备赚钱买煤气灶。
第一天，小j的工资为n元，之后每天他的工资都比前一天多d元。
已知煤气灶需要m元，求小j最少工作几天才能买到煤气灶。
第一天，小j的工资为n元，之后每天他的工资都比前一天多d元。
已知煤气灶需要m元，求小j最少工作几天才能买到煤气灶。
输入描述:
四个整数 n,m,d,x
分别表示小j第一天的工资，煤气灶的价格，工资每天的增长量，答案不超过x
输出描述:
一个数表示答案
备注:
0≤n,d≤1e9,n+d>0
1≤m≤1e18
1≤x≤1e9
题意：每天都能得到工资，一开始为n，每一天都可能在比前一天多领d（注意d可能为0），问最少多少天你领的工资的总和能超过买煤气灶需要的m元，天数不超过x
思路：求和问题，每天都可能多增加d的值，所以这是一个初值为n，公差为d的等差数列求和，等差数列求和公式：Sn=a0*n+(n*(n-1)*d/2),又注意到m最大是1e18,若要让等差数列之和Sn>=m,则Sn会超出long long的范围，所以要对公式进行变形，
设n为初值，in为天数，d为公差，m为总和至少需要大于的值，得到
n*in+(in*(in-1)*d)/2>=m
2*(n*in)+(in(in-1)*d)>=2*m
in*(in-1)*d>=2*(m-(n*in))
同时注意到1<=in<=x，所以就想到二分一下答案
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll n,m,d,x; 5 bool check(ll in){ 6 return in*(in-1)*d>=2*(m-(n*in)); 7 } 8 int main(){ 9 cin>>n>>m>>d>>x; 10 ll l=1,r=x,mid=(l+r)>>1; 11 while(l<r){ 12 if(check(mid))r=mid; 13 else l=mid+1; 14 mid=(l+r)>>1; 15 } 16 printf("%lld\n",mid); 17 } 18 /*** 19 n*in+(in*(in-1)*d)/2>=m 20 2*(n*in)+(in(in-1)*d)>=2*m 21 in*(in-1)*d>=2*(m-(n*in)) 22 ***/
查看45道真题和解析