题解归档 - cf535C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf535C
• 本地来源：problems/cf535C/idea.md
• 题目链接：https://codeforces.com/contest/535/problem/C
• 原始标题：cf535C — Tavas and Karafs

思路

cf535C — Tavas and Karafs

题意

无限序列 (s_i = A + (i-1)B)。一次 m-bite 可选至多 (m) 个未吃完的 Karafs，各自高度 (-1)；高度为 0 即吃完。

每个询问 ((l,t,m))：求最大 (r\ge l)，使 (s_l,\ldots,s_r) 可在 不超过 (t) 次 m-bite 内全部吃完；不存在则 (-1)。

关键引理

序列 (h_1,\ldots,h_k) 能在 (t) 次 m-bite 内吃完 当且仅当：

1. (\max h_i \le t)
2. (\sum h_i \le m\cdot t)

必要性：每次操作至多 (m) 个元素各 (-1)，(t) 次总减量 (\le mt)；单个元素最多被减 (t) 次。

充分性：对 (\sum h_i) 归纳。若非零元 (\ge m)，则恰有 (\le m) 个等于 (\max=t)（否则和已超 (mt)），对当前最大的 (m) 个各 (-1)；否则非零元 (<m)，全减。归纳到 ((m,t-1))。

做法

高度单调递增，对 (r) 二分。区间 ([l,r]) 为等差数列：

• (s_l = B(l-1)+A)，(s_r = B(r-1)+A)
• 和 ((r-l+1)(s_l+s_r)/2)
• 判定：(s_r\le t) 且 和 (\le mt)

复杂度

(O(n\log 10^6))，(n\le 10^5)。

验证

• 样例 + WSL 对拍 200 组（stress_wsl.sh，Kali 不可达时备用）

代码

来源：problems/cf535C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:22:25
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll A,B,n,l,t,m,sl,smid,sum,cnt,ans,le,ri,mi;
bool ok(ll r){
    cnt=r-l+1;
    smid=B*(r-1)+A;
    if(smid>t) return 0;
    sum=cnt*(sl+smid)/2;
    return sum<=m*t;
}
int main(){
    cin>>A>>B>>n;
    while(n--){
        cin>>l>>t>>m;
        sl=B*(l-1)+A;
        le=l;
        ri=1000000;
        ans=-1;
        while(le<=ri){
            mi=(le+ri)>>1;
            if(ok(mi)){
                ans=mi;
                le=mi+1;
            }else ri=mi-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}