用C语言解决饼干问题。要求对于每个测试点,有三行输入 第一行,输入两个正整数 n, q (n, q <= 20'0000),n 表示饼干的数量,q 表示询问的次数. 第二行,输入 n 个正整数 w [i],(w [i] <= 1000) 表示第 i 块饼干的饱腹感. 第三行,输入 p 个正整数 s [i], (s [i] <= 2'0000'0000), 表示 ly 第 i 次询问时的饱腹感上限.要求输出仅一行:q 个正整数,第 i 个数表示 ly 第 i 次询问时需要吃的饼干数.
时间: 2024-02-13 10:07:33 浏览: 121
好的,我理解了你的问题。这是一个很经典的问题,可以使用排序和前缀和的方法来解决。具体步骤如下:
1.读入 n, q 和 n 个正整数 w[i],存储在一个数组中。
2.将数组 w 排序,从小到大排列。
3.计算数组 w 的前缀和,即定义一个新的数组 sum,其中 sum[i] 表示前 i 个饼干的饱腹感之和。
4.读入 p 个正整数 s[i],对于每个 s[i],使用二分查找在数组 w 中找到最后一个小于等于 s[i] 的元素的下标 j,然后输出 j+1。
下面是 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
int main() {
int n, q, p;
scanf("%d %d", &n, &q);
int *w = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
}
qsort(w, n, sizeof(int), cmp);
int *sum = (int*)malloc(n * sizeof(int));
sum[0] = w[0];
for (int i = 1; i < n; i++) {
sum[i] = sum[i-1] + w[i];
}
for (int i = 0; i < q; i++) {
scanf("%d", &p);
int left = 0, right = n-1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (w[mid] <= p) {
left = mid + 1;
} else {
right = mid - 1;
}
}
printf("%d ", left);
}
free(w);
free(sum);
return 0;
}
```
希望能够帮助到你!
阅读全文