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

题目传送门

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

 typedef long long ll;

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

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

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

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

     }

     return ;
 }