用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 22:02:59 浏览: 78
好的,这个问题需要使用贪心算法来解决。首先我们将流量包按照大小从小到大排序。然后对于每一个游戏,我们从最大的流量包开始,依次尝试使用,直到可以满足游戏的流量需求。
具体实现如下:
```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;
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;
for (int j = n - 1; j >= 0; j--) {
if (x <= 0) break;
if (x > traffic[j]) {
ans += x / traffic[j];
x %= traffic[j];
}
}
printf("%d\n", ans);
}
free(traffic);
return 0;
}
```
首先读入流量包的数量 n 和游戏的数量 q,然后读入 n 个流量包的大小,存放在 traffic 数组中。接着对 traffic 数组进行排序。然后对于每一个游戏,我们从最大的流量包开始,依次尝试使用,直到可以满足游戏的流量需求。最后输出需要购买的流量包数量。
需要注意的是,题目中给出的流量和游戏的流量都很大,为了避免整型溢出,我们需要使用 long long 类型来存储游戏的流量。
阅读全文