阿里笔试4.3场（附代码）+ 前6场代码链接

/*
对于每一位数据，每次进行一次查找操作和插入操作
首先从左向右遍历，查找比其大的左值中的最小值，再插入该值
再从右向左遍历，查找比其小的右值中的最大值，再插入该值
注意，如果该值为最大、最小值，则该值标记为无效
统计所有有效值里，左值整除右值的数量
时间复杂度O(nlogn)，空间复杂度O(n)
*/

#include<iostream>
#include<vector>
using namespace std;

void insert(vector<long long> &sortlist, long long val) {
    if(sortlist.empty()) {
        sortlist.push_back(val);
    }
    int l = 0, r = int(sortlist.size())-1;
    int mid;
    while(l <= r) {
        mid = (l+r)/2;
        if(sortlist[mid] == val) {
            return;
        }
        else if(sortlist[mid] > val){
            r = mid-1;
        }
        else {
            l = mid+1;
        }
    }
    sortlist.insert(sortlist.begin()+l, val);
    return;
}

long long valfind(vector<long long> &sortlist, long long val, bool findmin) {
    if(sortlist.empty()) {
        return val;
    }
    int l = 0, r = int(sortlist.size())-1;
    int mid;
    long long res = val;
    
    if(findmin) {
        while(l <= r) {
            mid = (l+r)/2;
            if(sortlist[mid] >= val) {
                r = mid-1;
            }
            else {
                res = sortlist[mid];
                l = mid+1;
            }
        }
    }
    else {
        while(l <= r) {
            mid = (l+r)/2;
            if(sortlist[mid] <= val) {
                l = mid+1;
            }
            else {
                res = sortlist[mid];
                r = mid-1;
            }
        }
    }
    return res;
}

int countvalnum(vector<long long> &v) {
    if(v.empty()) {
        return 0;
    }
    
    int res = 0, i;
    long long recmax[v.size()];
    long long recmin[v.size()];
    bool isvalid[v.size()];
    vector<long long> sortlist;
    
    for(i = 0; i < v.size(); i++) {
        isvalid[i] = 1;
    }
    
    for(i = 0; i < v.size(); i++) {
        recmax[i] = valfind(sortlist, v[i], 0);
        if(recmax[i] == v[i]) {
            isvalid[i] = 0;
        }
        insert(sortlist, v[i]);
    }
    sortlist.clear();
    for(i = int(v.size()-1); i >= 0; i--) {
        recmin[i] = valfind(sortlist, v[i], 1);
        if(recmin[i] == v[i]) {
            isvalid[i] = 0;
        }
        insert(sortlist, v[i]);
    }
    
    for(i = 1; i < v.size()-1; i++) {
        if(isvalid[i] && recmax[i]%recmin[i] == 0) {
            res++;
        }
    }
    return res;
}

int main() {
    int n;
    cin>>n;
    vector<long long> v;
    
    int i, tmp;
    for(i = 0; i < n; i++) {
        cin>>tmp;
        v.push_back(tmp);
    }
    cout<<countvalnum(v)<<endl;
    return 0;
}

/*
bfs:先把第一行所有元素入队，每次判断队首元素上下左右方向上，如发现其路径比从当前队首位置到其更长，入队。
队列空则更新结束。
*/
#include<iostream>
#include<queue>
#include<vector>
#include<math.h>
using namespace std;

struct prs {
    int x;
    int y;
};

void update(queue<prs> &q, vector<vector<int> > &path, vector<vector<int> > &maze) {
    prs tmp = q.front();
    prs newtmp;
    int nowdis = path[tmp.x][tmp.y] + maze[tmp.x][tmp.y];
    if(tmp.x - 1 > 0 && path[tmp.x - 1][tmp.y] > nowdis) {
        path[tmp.x - 1][tmp.y] = nowdis;
        newtmp.x = tmp.x-1;
        newtmp.y = tmp.y;
        q.push(newtmp);
    }
    if(tmp.x + 1 < path.size() && path[tmp.x + 1][tmp.y] > nowdis) {
        path[tmp.x + 1][tmp.y] = nowdis;
        newtmp.x = tmp.x+1;
        newtmp.y = tmp.y;
        q.push(newtmp);
    }
    if(tmp.y - 1 > 0 && path[tmp.x][tmp.y - 1] > nowdis) {
        path[tmp.x][tmp.y-1] = nowdis;
        newtmp.x = tmp.x;
        newtmp.y = tmp.y-1;
        q.push(newtmp);
    }
    if(tmp.y + 1 < path[0].size() && path[tmp.x][tmp.y + 1] > nowdis) {
        path[tmp.x][tmp.y+1] = nowdis;
        newtmp.x = tmp.x;
        newtmp.y = tmp.y+1;
        q.push(newtmp);
    }
    q.pop();
    return;
}

int minpath(vector<vector<int> > &maze) {
    if(maze.empty() || maze[0].empty()) {
        return 0;
    }
    vector<vector<int> > path;
    vector<int> vtmp;
    queue<prs> q;
    prs tmp;
    int res = INT_MAX;
    int i,j;
    
    for(j = 0; j < maze[0].size(); j++) {
        vtmp.push_back(0);
        tmp.x = 0;
        tmp.y = j;
        q.push(tmp);
    }
    path.push_back(vtmp);
    vtmp.clear();
    
    for(j = 0; j < maze[0].size(); j++) {
        vtmp.push_back(INT_MAX);
    }
    for(i = 1; i < maze.size(); i++) {
        path.push_back(vtmp);
    }
    
    while(!q.empty()) {
        update(q, path, maze);
    }
    
    for(j = 0; j < maze[0].size(); j++) {
        res = min(res, maze[maze.size()-1][j] + path[maze.size()-1][j]);
    }
    return res;
}

int main() {
    int n, m;
    cin>>n>>m;
    int i,j;
    vector<vector<int> > maze;
    vector<int> vtmp;
    int tmp;
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            cin>>tmp;
            vtmp.push_back(tmp);
        }
        maze.push_back(vtmp);
        vtmp.clear();
    }
    
    cout<<minpath(maze)<<endl;
    return 0;
}