C++实现巧克力装包问题：最大装包巧克力数量

#include #include #include using namespace std;

const int maxn = 50005; const int maxm = 1e5+5;

int n, m; int a[maxn]; long long q[maxm];

bool check(int x, long long w) { long long cnt = 0; for (int i = 1; i <= x; i++) { cnt += (long long)floor(sqrt(w*1.0/a[i])); } return cnt >= q[m]; }

int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= m; i++) { cin >> q[i]; } sort(a+1, a+n+1); sort(q+1, q+m+1); int l = 0, r = n, mid, ans; while (l <= r) { mid = (l + r) >> 1; if (check(mid, q[1])) { ans = mid; r = mid - 1; } else { l = mid + 1; } } for (int i = 1; i <= m; i++) { if (q[i] > (long long)a[1]*a[1]*ans) { cout << 0 << " "; continue; } l = 1, r = ans; while (l <= r) { mid = (l + r) >> 1; if (check(mid, q[i])) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans << " "; } return 0; }