有n个巧克力每个巧克力都是厚度一样的正方形巧克力板边长分别为a1a2an认为第i个巧克力的重量为ai²。第一行输入两个整数n和m表示巧克力数量和小美询问数量。第二行n个整数a1a2an表示n块正方形巧克力板的边长注意不能将巧克力板进行拆分第三行m个整数q1q2qn第i个整数qi表示询问：如果小美选择一个能装qi重量的钱包最多能装多少巧克力板？1=nm=500001=ai=10四次方1=qi=10十八次方输出一行m个整数表示每次询问的答案不用解释直接用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; }