cf535 C. Tavas and Karafs

本文主要是介绍cf535 C. Tavas and Karafs，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意：

给定一个递增等差数列，每次操作可把不超过 \(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;
    }
}

这篇关于cf535 C. Tavas and Karafs的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！