Time 2000ms RAM 32767K
题面：
蒜头君在和他的朋友们一起玩一个游戏。由于蒜头君的机智，这个 游戏由蒜头君担任裁判。
首先，蒜头君会给他们一人一个编号，并且每个人的编号都不相同。接下来的每一回合，蒜头君会给一个数，编号不超过它的最大编号的人要报出自己的编号。如果没有人的编号比蒜头君给出的数要小，那么编号最小的人要报出自己的编号。每个人可以重复报号。
蒜头君会按照一个列表顺次报出每个回合的数，他的朋友们想知道每回合报出的编号应该是多少。你能帮帮他们吗？
输入格式
输入数据共 3 行。第一行有两个整数 n,m （1≤ n ≤ 10^5,1 ≤ m ≤ 10^5），分别表示参与游戏的蒜头君朋友的个数，和游戏的回合数。
第二行 n个整数ai（1 ≤ ai ≤ 10^8），表示朋友们每个人的编号。
第三行 m 个整数qi（1 ≤ qi ≤ 10^8），表示每回合蒜头君给的数字。
输出格式
输出共一行，输出 m个整数，表示每回合报出的编号。每两个整数之间有一个空格，最后一个整数后面没有空格。
样例输入
5 5 1 5 10 15 20 3 6 12 18 24
样例输出
1 5 10 15 20
思路：
将输入分别储存为 编号数组 和 报数数组 ，为了提高查找效率，先将编号数组排序，然后用二分查找算法在已排序的数组中找数。
分析：
- 由于输入的数组长度不确定，相比于开创一个巨大的数组，更好的选择是使用
vector容器储存数据； - 排序算法可以自己实现一种算法（如冒泡法，归并法），也可以使用
qsort或者std::sort实现； - 查找算法我们选择二分查找法。
实现（C++）：
#include<iostream>
#include<vector>
#include<algorithm>
using std::cout;
using std::cin;
using std::endl;
using std::sort;
using std::vector;
int binsearch(vector<int>&a, int lef, int rig, int e) {
while (lef <= rig) {
int mid = (lef + rig) >> 1;
if(a[mid] > e) rig = mid - 1;
else lef = mid + 1;
}
if(rig<0)rig=0;
return rig;
}
int main() {
//n：参与人数，m：游戏回合数
int n,m;
cin >> n >> m;
vector<int>array1;
vector<int>array2;
//输入
int input;
for(int i=0;i<n;i++) {
cin >> input;
array1.push_back(input);
}
for(int i=0;i<m;i++) {
cin >> input;
array2.push_back(input);
}
//排序
sort(
&array1[0],
&array1[n]
);
//二分法查找
int output;
for(int i=0;i<m;i++) {
output = binsearch(array1,0,n-1,array2[i]);
if(i==m-1) {
cout << array1[output] <<endl;
}
else {
cout << array1[output] <<" ";
}
}
return 0;
}
Note：
- 第一次提交的时候几乎全错了。情形如下：
出现了编号数组中未出现的0，于是在rig返回前插入输出，发现rig = -1于是在return rig；前加入判断，完成。
terminal
- 第二次提交时前五个正确，后五个超时了。原因是原先
binsearch()函数使用的是vector<int>a形参，形实结合时是值传递，导致额外的一次拷贝操作，带来的时间开销非常大。改成引用作为形参：vector<int>&a，完成。另外，使用vector前，
#include<vector>
using std::vector;
- 向
vector中填充数据，比较好的做法是：
int input;
for(int i=0;i<n;i++) {
cin >> input;
array1.push_back(input);
}
而不是：
for(int i=0;i<n;i++) {
cin >> array[i];
}
因为后者存在着数组越界的隐患。
-
std::sort的使用：
#include<algorithm>
using std::sort;
...
//举例1
vector<int> a = { 2, 4, 5, 3, 1 };
sort(
begin(a),
end(a),
[](int x, int y){ return x >= y; }
);
//举例2
vector<int>b;
cin << n;
int input;
for(int i=0;i<n;i++) {
cin >> input;
b.push_back(input);
}
sort(
&b[0],
&b[n],
[](int x, int y){ return x < y; }
);
