【题意】这题看了好久好久!其实就是个二分水题!
首先给出a,b,n
这是一个由a开头,b为公差,长度无限的等差数列
然后n个询问
输入l,t,m
取这个数列从l开始,m个数,每一次这个数列中所有的数字-1
当首尾变成0的时候,可以向后移,问最后t次之后,最长的0序列的右边界是多少
那么我们首先可以确定,对于这个最终的序列而言,假设右边界为r
那么max(h1,h2,...hr)<=t && h1+h2+...hr<=t*m
对于这两个条件,我们进行二分即可【AC代码】
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a,b,n;
ll l,t,m;
ll cal(ll x){
return a+(x-1)*b;
}
ll getSum(ll r){
return (cal(r)+cal(l))*(r-l+1)/2; //等差数列求和
}
int main(){
cin>>a>>b>>n;
while(n--){
cin>>l>>t>>m;
if(cal(l)>t) cout<<"-1"<<endl;
else{
ll lb = l,rb = (t-a)/b+1, mid;
while(lb<=rb){
mid = (lb+rb)>>1;
if(getSum(mid)<=t*m) lb = mid+1;
else rb = mid-1;
}
cout<<lb-1<<endl;
}
}
return 0;
}