楼尔邦德

楼尔邦德

时间限制：2 sec

空间限制：256 MB

问题描述

给定包含 n 个数的序列 A。

再给出 Q 个询问，每个询问包含一个数 x，询问的是序列 A 中不小于 x 的最小整数是多少（无解输出-1）。

输入格式

第一行一个数 n，表示序列长度。

第二行 n 个用空格隔开的正整数，描述序列中的每一个元素。保证这些元素都不会超过

10^9。

第三行一个正整数 Q，表示询问个数。

接下来 Q 行，每行一个正整数 x，描述一个询问。

输格式

输出 Q 行依次回答 Q 个询问，每行一个正整数，表示对应询问的答案。

样例输入

样例输

数据范围

对于 50% 的数据，保证 n<=2000。

对于 100% 的数据，保证 n<=300,000。

提示

[如果我们先将原序列排序，那么我们就可以在它上面进行二分查找啦！]

[STL 库中有二分查找的函数 std::lower_bound ，你可以学习一下它的使用。当然啦， 作为初学者，还是建议自己实现二分查找哦！]

代码

#include <iostream> #include<vector>

#include <algorithm>// std::lower_bound, std::upper_bound, std::sort #pragma warning(disable:4996)

using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */

// 本函数传入数组 a 及所有询问，你需要求解所有询问并一并返回

// n：序列 a 的长度

// a：存储了序列 a

// Q：询问个数

// query：依次存储了所有询问的参数 x

// 返回值：一个 vector<int>，依次存放各询问的答案

vector<int> getAnswer(int n, vector<int> a, int Q, vector<int> query) {

vector<int> ans;

sort(a.begin(), a.end());

vector<int>::iterator low;

for (int i = 0; i < Q; i++)

{

low = lower_bound(a.begin(), a.end(), query[i]);

if (low == a.end())

ans.push_back(-1);

else

ans.push_back(a[low-a.begin()]);

}

return ans;

/* 请在这里设计你的算法 */

}

// ================= 代码实现结束 =================

int main() {

int n, Q, tmp;

vector<int> a, query;

a.reserve(300000);

query.reserve(300000);

a.clear();

query.clear();

scanf("%d", &n);

for (int i = 0; i < n; ++i) {

scanf("%d", &tmp);

a.push_back(tmp);

}

scanf("%d", &Q);

for (int i = 0; i < Q; ++i) {

scanf("%d", &tmp);

query.push_back(tmp);

}

vector<int> ans = getAnswer(n, a, Q, query);

for (int i = 0; i < Q; ++i)

printf("%d\n", ans[i]);

return 0;

}