计蒜客_新报数游戏

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; }
    );

计蒜客_新报数游戏

题面：

思路：

分析：

实现（C++）：

Note：

推荐阅读更多精彩内容