[二分]煤气灶

链接：https://ac.nowcoder.com/acm/problem/21860
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

小j开始打工，准备赚钱买煤气灶。
第一天，小j的工资为n元，之后每天他的工资都比前一天多d元。
已知煤气灶需要m元，求小j最少工作几天才能买到煤气灶。

输入描述:

四个整数 n,m,d,x
分别表示小j第一天的工资，煤气灶的价格，工资每天的增长量，答案不超过x

输出描述:

一个数表示答案

示例1

输入

复制

10 100 20 100

输出

复制

4

说明

10+30+50+70>=100

备注:

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，所以就想到二分一下答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,d,x;
bool check(ll in){
    return in*(in-1)*d>=2*(m-(n*in));
}
int main(){
    cin>>n>>m>>d>>x;
    ll l=1,r=x,mid=(l+r)>>1;
    while(l<r){
        if(check(mid))r=mid;
        else l=mid+1;
        mid=(l+r)>>1;
    }
    printf("%lld\n",mid);
}
/***
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))
***/