题解：P17865 [FJCPC 2026] 排考场

hydk2012 · 2026-11-12 18:46:13 · 题解

思路

检测到关键词：最大可能的最小列间距。发现其间距越大可放的人数越少，有单调性，考虑二分答案。

每次二分出来的数就看这样子间距考场人数最大能不能放下 n 个人即可。

计算每一个考场可放人数。不难发现其就是将一列人和 x 列空桌分为一组。计算有几组。注意如果其有余下的，还可以再放一组。所有的可放列数再乘上每一列的座位数即可。

Code：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,m;
struct node
{
    int r,c;
}a[100005];
bool check(int x)
{
    int can=0;
    for(int i=1;i<=m;i++)
    {
        int cnt=a[i].c/(x+1)+(bool)(a[i].c%(x+1));
        can+=cnt*a[i].r;
    }
    return can>=n;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>a[i].r>>a[i].c;
    int l=0,r=1e18,mid,ans=-1;
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid))
        {
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }
    cout<<ans;
    return 0;
}