C++ 实现巧克力装包问题：二分查找最优解

#include #include #include using namespace std;

int n, m; long long a[50005], q[50005];

bool check(long long x) { // 判断x是否可行 long long cnt = 0; for (int i = 1; i <= n; i++) { cnt += a[i] * a[i]; // 累加当前巧克力的重量 if (cnt > x) return false; // 超出了x的限制，不可行 } return true; }

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]; } long long l = 0, r = 1e36; // 左右边界 while (l < r) { // 二分答案 long long mid = (l + r) / 2; if (check(mid)) { // 可行，限制更小 r = mid; } else { // 不可行，限制更大 l = mid + 1; } } for (int i = 1; i <= m; i++) { // 输出答案 long long cnt = 0; for (int j = 1; j <= n; j++) { cnt += a[j] * a[j]; if (cnt > q[i]) { cout << j - 1 << " "; break; } if (j == n) { cout << n << " "; } } } return 0; }