CodeForces 535C Tavas and Karafs —

CodeForces 535C Tavas and Karafs —— 二分

　　题意：给出一个无限长度的等差数列（递增），每次可以让从l开始的m个减少1，如果某个位置已经是0了，那么可以顺延到下一位减少1，这样的操作最多t次，问t次操作以后从l开始的最长0序列的最大右边界r是多少。

　　分析：由题意可以挖掘出两个条件：l~r中最大的值（因为是递增的，即r的值）必定不大于t；同时，t*m要大于或等于这一段的和。那么根据这两个条件进行二分即可。

　　细节：二分的右端点inf不能设置的太大，否则第一次的mid可能就会爆long long。

　　代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 using namespace std;
 5 const int N = 200000+5;
 6 typedef long long ll;
 7 
 8 const ll inf = (ll)0x3f3f3f3f;
 9 
10 int main()
11 {
12     int a,b,n,l,t,m;
13     scanf("%d%d%d",&a,&b,&n);
14     while(n--)
15     {
16         scanf("%d%d%d",&l,&t,&m);
17         ll st = l, ed = inf;
18         ll r = -1;
19         while(st<=ed)
20         {
21             ll mid = st + ed >> 1;
22             ll sum = (2*a+b*(l+mid-2))*(mid-l+1)/2;
23             ll maxn = a + b*(mid-1);
24             if(maxn>(ll)t || (ll)m*t < sum)
25             {
26                 ed = mid - 1;
27                 continue;
28             }
29             else
30             {
31                 r = mid;
32                 st = mid + 1;
33             }
34         }
35         printf("%I64d
",r);
36     }
37     return 0;
38 }