http://codeforces.com/problemset/problem/535/C
题意 有一个等差数列 从A开始 公差为B 然后n个询问 每个询问给定l,t,m 然后要求如果每次可以最多选择m个数 使这m个数-1 那么在t次操作中可以使l为左端点的最长序列中使所有数为0 输出这个最长序列的右端序号 定理 序列h1,h2,...,hn 可以在t次时间内(每次至多让m个元素减少1) 全部减小为0 当且仅当 max(h1, h2, ..., hn) <= t && h1 + h2 + ... + hn <= m*t 那么就可以二分右端点来解决了 下限为l 上限为hi不超过t的最大i #include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<stack> #include<set> #include<bitset> using namespace std; typedef long long LL; LL a, b, n, l, t, m; LL getv(LL p) { return a + (p - 1) * b; } LL getsum(LL r) { return (getv(r) + getv(l)) * (r - l + 1) / 2; } int main() { cin.sync_with_stdio(false); cin>>a>>b>>n; while(n--) { cin>>l>>t>>m; if(getv(l) > t) cout<<"-1\n"; else { LL le = l, ri = (t - a) / b + 1, mid; while(le <= ri) { mid = (ri + le) / 2; if(getsum(mid) <= t * m) le = mid + 1; else ri = mid - 1; } cout<<le-1<<endl; } } return 0; }