题解：P17865 [FJCPC 2026] 排考场

· · 题解

思路

我们设列间距为 x ，如果列间距 x 符合条件，那么列间距 x - 1 也一定符合条件，那么便有了单调性，我们便可以用二分，因为中间是隔了 x 列，那么每 x + 1 列才能有一列可以放，那么累加时就要累加 (\max(0, \lfloor \frac{c_i - 1}{x + 1} \rfloor) + 1) \times r_i ，其中 c_i - 1 是因为第一列一定能放，也不要忘记后面要加一，加上第一列。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
int n,r[MAXN],c[MAXN],m;
bool check(int x){
    int ans=0;
    for(int i=1;i<=m;i++)
        ans+=(max(0ll,(c[i]-1)/(x+1))+1)*r[i];
    return ans>=n;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>r[i]>>c[i];
    int L=0,R=1e18+1,M;
    while(L+1<R){
        M=L+R>>1;
        if(check(M))L=M;
        else R=M;
    }cout<<L;
    return 0;
}