用c语言和二分查找解决这个问题描述:On the way to City Fun, Ming wants to download a mobile game. Ming is choosing which game to download when a message pops up on his phone telling him that he has run out of traffic (流量). Since the trip is so long, Ming decides to buy some traffic packs (流量包). Each traffic pack can be bought only once. Ming wants to know the minimum number of traffic packs he needs to buy for each game. 输入:The first line contains two integers n and q (1<=n,q<=100000), representing the number of traffic packs and the number of games respectively (分别地). The second line contains n integers, and the ith integer represents the amount of traffic Ai in the ith traffic pack (1<=Ai<=10^9). The third line contains q integers, and the ith integer represents the amount of traffic used by the ith game xi (1<=xi<=10^18). 输出:For the ith line, output an integer W representing the number of traffic packs that Ming needs to buy for the ith game.:
时间: 2024-02-14 10:02:59 浏览: 58
好的,这个问题可以使用二分查找来解决。我们首先将流量包按照大小从小到大排序,然后对于每一个游戏,我们可以使用二分查找来找到最小的满足游戏流量需求的流量包。
具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
int cmp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int binary_search(int* traffic, int l, int r, long long x) {
while (l < r) {
int mid = (l + r) / 2;
if (traffic[mid] < x) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
int main() {
int n, q;
scanf("%d%d", &n, &q);
int* traffic = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &traffic[i]);
}
qsort(traffic, n, sizeof(int), cmp);
for (int i = 0; i < q; i++) {
long long x;
scanf("%lld", &x);
int ans = 0;
while (x > 0) {
int idx = binary_search(traffic, 0, n, x);
if (idx >= n) break;
x -= traffic[idx];
ans++;
}
printf("%d\n", ans);
}
free(traffic);
return 0;
}
```
首先读入流量包的数量 n 和游戏的数量 q,然后读入 n 个流量包的大小,存放在 traffic 数组中。接着对 traffic 数组进行排序。然后对于每一个游戏,我们使用二分查找来找到最小的满足游戏流量需求的流量包,并将其从游戏流量中减去。如果不存在满足游戏流量需求的流量包,则退出循环。最后输出需要购买的流量包数量。
需要注意的是,题目中给出的流量和游戏的流量都很大,为了避免整型溢出,我们需要使用 long long 类型来存储游戏的流量。
阅读全文