二分搜索 Codeforces Round #299 (Div. 2) C. Tavas and Karafs

题目传送门

/*
    题意：给定一个数列，求最大的r使得[l,r]的数字能在t次全变为0，每一次可以在m的长度内减1
    二分搜索：搜索r，求出sum <= t * m的最大的r
    详细解释：http://blog.csdn.net/libin56842/article/details/45082747
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

typedef long long ll;

const int MAXN = 1e4 + 10;
const int INF = 0x3f3f3f3f;
ll A, B, n, l, t, m;

ll cal(ll x)    {return A + (x - 1) * B;}

ll get_sum(ll l, ll r)
{
    return (cal (l) + cal (r)) * (r - l + 1) / 2;
}

int main(void)        //Codeforces Round #299 (Div. 2) C. Tavas and Karafs
{
    while (scanf ("%I64d%I64d%I64d", &A, &B, &n) == 3)
    {
        for (int i=1; i<=n; ++i)
        {
            scanf ("%I64d%I64d%I64d", &l, &t, &m);
            if (cal (l) > t)    {puts ("-1");    continue;}
            ll x = l;    ll r = (t - A) / B + 1;
            while (x <= r)
            {
                ll mid = (x + r) / 2;
                if (get_sum (l, mid) <= t * m)    x = mid + 1;
                else    r = mid - 1;
            }
            printf ("%d
", r);
        }

    }

    return 0;
}