Time 2000ms RAM 32767K
題面：
蒜頭君在和他的朋友們一起玩一個游戲晚缩。由于蒜頭君的機智，這個 游戲由蒜頭君擔(dān)任裁判甘磨。
首先橡羞，蒜頭君會給他們一人一個編號，并且每個人的編號都不相同济舆。接下來的每一回合，蒜頭君會給一個數(shù)莺债，編號不超過它的最大編號的人要報出自己的編號滋觉。如果沒有人的編號比蒜頭君給出的數(shù)要小，那么編號最小的人要報出自己的編號齐邦。每個人可以重復(fù)報號椎侠。
蒜頭君會按照一個列表順次報出每個回合的數(shù)，他的朋友們想知道每回合報出的編號應(yīng)該是多少措拇。你能幫幫他們嗎我纪？
輸入格式
輸入數(shù)據(jù)共 3 行。第一行有兩個整數(shù) n,m （1≤ n ≤ 10^5,1 ≤ m ≤ 10^5），分別表示參與游戲的蒜頭君朋友的個數(shù)浅悉，和游戲的回合數(shù)趟据。
第二行 n個整數(shù)ai（1 ≤ ai ≤ 10^8），表示朋友們每個人的編號术健。
第三行 m 個整數(shù)qi（1 ≤ qi ≤ 10^8）汹碱，表示每回合蒜頭君給的數(shù)字。
輸出格式
輸出共一行荞估，輸出 m個整數(shù)咳促，表示每回合報出的編號。每兩個整數(shù)之間有一個空格勘伺，最后一個整數(shù)后面沒有空格跪腹。
樣例輸入
5 5 1 5 10 15 20 3 6 12 18 24
樣例輸出
1 5 10 15 20
思路：
將輸入分別儲存為 編號數(shù)組 和 報數(shù)數(shù)組 ，為了提高查找效率飞醉，先將編號數(shù)組排序尺迂，然后用二分查找算法在已排序的數(shù)組中找數(shù)。
分析：
- 由于輸入的數(shù)組長度不確定冒掌，相比于開創(chuàng)一個巨大的數(shù)組噪裕，更好的選擇是使用
vector容器儲存數(shù)據(jù)； - 排序算法可以自己實現(xiàn)一種算法（如冒泡法股毫，歸并法）膳音，也可以使用
qsort或者std::sort實現(xiàn)； - 查找算法我們選擇二分查找法铃诬。
實現(xiàn)（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：參與人數(shù)祭陷，m：游戲回合數(shù)
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：
- 第一次提交的時候幾乎全錯了。情形如下：
出現(xiàn)了編號數(shù)組中未出現(xiàn)的0趣席，于是在rig返回前插入輸出兵志，發(fā)現(xiàn)rig = -1于是在return rig；前加入判斷宣肚，完成想罕。
terminal
- 第二次提交時前五個正確，后五個超時了霉涨。原因是原先
binsearch()函數(shù)使用的是vector<int>a形參按价，形實結(jié)合時是值傳遞，導(dǎo)致額外的一次拷貝操作笙瑟，帶來的時間開銷非常大楼镐。改成引用作為形參：vector<int>&a，完成往枷。另外框产，使用vector前凄杯，
#include<vector>
using std::vector;
- 向
vector中填充數(shù)據(jù)，比較好的做法是：
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];
}
因為后者存在著數(shù)組越界的隱患秉宿。
-
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; }
);
