题意:
给定一个递增等差数列,每次操作可把不超过 \(m\) 个不同的位置减 1
\(q\) 次询问,每次 \(l,t,m\),输出用不超过 \(t\) 次操作能把 \([l,r]\) 变成 0 的最大 \(r\)
思路:
首先显然二分。然后怎么判断呢?结论是合法当且仅当 \(\sum a_i \le mt\) 且 \(\max a_i \le t\)
显然这是必要的。充分性也很好证:
若 \([l,r]\) 中有大于等于 \(m\) 个非零数,则最大值的数量至多 \(m\) 个(否则总和可能超过 \(mt\))。我们从大到小选 \(m\) 个数,把它们都减 1。注意这不会改变 \(\sum a_i \le mt\) 的关系。重复此操作直到下一种情况。
若非零数小于 \(m\) 个,那就把所有非零数减 1。显然这是可行的!
ll A, B, q, L, t, m; bool ok(ll R) { return A+B*(R-1) <= t && (A+B*(L-1)+A+B*(R-1))*(R-L+1)/2 <= t*m; } void sol() { cin >> A >> B >> q; while(q--) { cin >> L >> t >> m; ll l = L-1, r = 1e7; while(l < r) { ll mid = (l + r + 1) / 2; if(ok(mid)) l = mid; else r = mid - 1; } cout << (l < L ? -1ll : l) << endl; } }