Quests题解
题目链接
这题的rating是1500，是我上个月写的。闲着没事再写一遍，发现不能一遍过，写个题解。
首先注意数据范围， 1 0 16 10^{16} 1016，要开 l o n g l o n g long~long long long。为了省事直接#define int long long
我们只需要将数组进行从大到小排序排序，然后尝试每个 d d d的数值，得到最大的就可以。当然，这里使用二分来进行优化
int l = -1,r = d + 1; while(l < r) { int mid = l + r + 1 >> 1; if(check(mid)) l = mid; else r = mid - 1; } 如果最后的结果是-1，则说明不存在 k k k值；如果结果是 d + 1 d+1 d+1，则说明 k k k可以是任意值
然后是check函数
bool ckeck(int k) { int res = 0; for(int i = 0;i < d;++i) { int j = i % (k + 1); if(j < n) res += a[i]; } return res >= m; } 最后我们来看看完整代码
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define rall(a) a.rbegin(), a.rend() #define vint vector<int> void solve() { int n, m, d; cin >> n >> m >> d; vint a(n); for (int i = 0; i < n; ++i) cin >> a[i]; sort(rall(a)); auto check = [&](int k) { int res = 0; for (int i = 0; i < d; ++i) { int j = i % (k + 1); if (j < n) res += a[j]; } return res >= m; }; int l = -1, r = d + 1; while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } if (l == -1) cout << "Impossible" << endl; else if (l == d + 1) cout << "Infinity" << endl; else cout << l << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int t = 1; cin >> t; while (t--) solve(); return 0; } 