题解：P17865 [FJCPC 2026] 排考场

· · 题解

啊，又是一道套路题。

选择算法

直接通过最小值最大化和单调性推出要用二分答案。

check 函数

首先定义 check(x) 表示最小间距为 x 时可不可以坐下 n 个人。

  1. 注意到如果一间教室只用了一列，那么就不需要考虑，因为他的间距为 \inf。
  2. 否则如果间距为 k，坐了 d 列，那么教室的列数至少为 1+(k-1)(d+1)。
  3. 从而推出如果如果一个教室有 r 行 c 列，间距为 d，那么能够坐下 r\cdot \lfloor\dfrac{c+d}{d+1}\rfloor 个人，然后只要把每个教室能坐下的人数加起来看是不是 >n 就好了。

    代码

    #include <bits/stdc++.h>
using namespace std ;
#define int long long
int n , m , R[100005] , c[100005] , l , r = 1e9 ;
bool check(int mid) {
 int sum = 0 ;
 for(int i = 1 ; i <= m ; i ++) {
     sum += (c[i] + mid) / (mid + 1) * R[i] ;
     if(sum >= n) {//有1e5个教室，每个教室能坐下1e9*1e9=1e18个人，总共1e5*1e18=1e23个人，肯定会超long long（只不过你用__int128就当我没说）
         return 1 ;
     }
 }
 return 0 ;
}
signed main() {
 cin >> n >> m ;
 for(int i = 1 ; i <= m ; i ++) {
     cin >> R[i] >> c[i] ;
 }
 while(l + 1 < r) {
     int mid = (l + r) / 2 ;
     if(check(mid)) {
         l = mid ;
     } else {
         r = mid ;
     }
 }
 cout << l ;
 return 0 ;
}

    设 k=10^9 表示间距的最大值