输入 第一行包含两个整数 n 和 q (1<=n,q<=100000),分别表示流量包的数量和游戏的数量(分别地)。第二行包含 n 个整数,第 i 个整数表示第 i 个流量包中的流量 Ai(1<=Ai<=10^9)。第三行包含 q 整数,第 i 个整数表示第 i 个游戏 xi 使用的流量 (1<=xi<=10^18)。 输出 对于第 i 行,输出一个整数 W,表示 Ming 需要为第 i 个游戏购买的流量包数量。用c++写代码
时间: 2024-02-18 19:03:51 浏览: 169
以下是一份 C++ 的代码实现,通过二分搜索来解决该问题:
```c++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(arr.begin(), arr.end()); // 将流量包按从小到大排序
while (q--) {
long long x;
cin >> x;
int left = 0, right = n - 1, ans = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] >= x) {
ans = mid; // 更新最优解
right = mid - 1; // 继续在左侧查找
} else {
left = mid + 1; // 继续在右侧查找
}
}
cout << ans + 1 << endl; // 注意加 1,因为下标是从 0 开始的
}
return 0;
}
```
首先读入流量包数量 `n` 和游戏数量 `q`,然后读入所有的流量包大小,并将其从小到大排序。接着循环读入每个游戏需要的流量 `x`,对于每个流量 `x`,在流量包数组中进行二分搜索,找到最小的流量包大小 `a`,使得 `a >= x`,最后输出 `a` 的下标加 1(因为下标是从 0 开始的,而题目要求从 1 开始编号)。
阅读全文