2 条题解
-
0
考虑贪心选择。不浪费长凳长度。
此时长凳的摆放方式如下：
也就是说若选择长凳长度为 q，则每行必须空出 m/q 个位置。也就是说，每行最多选择 m−m/q 个位置，总共最多选 n∗(m−m/q) 个位置。
二分 q 即可。若 q≥k，则代表能够坐下所有人；若 q<k 则代表不能。
时间复杂度：O(lognlogm)。
-
morgen
@ 2025-10-26 16:07:05
#include<bits/stdc++.h> using namespace std; #define int long long int n,m,k; bool check(int x){ int sum = n * (m - (m/x)); return sum >= k; } void solve() { cin >> n >> m >> k; int l = 1,r = m + 1; int ans = m; while(l <= r){ int mid = (l + r) >> 1; if(check(mid)){ ans = mid; r = mid - 1; } else l = mid + 1; } cout << ans - 1 << endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int T = 1; cin >> T; while (T--) solve(); return 0; }
-