京东2021-10-30笔试

投的是运筹优化算法岗.

选择题30道（30X2 分）——涵盖多选和单选题

考察的内容大致包括：C++、Java、Python和SQL的编程基础，数据结构基本内容、机器学习和深度学习一些前沿内容、还有一道组合数学的题目（考的双亲问题）.

编程题一（20分）

时间限制： 5000MS
内存限制： 655360KB

问题描述：

小明在学校里兼职做化学实验室的管理员，学生做完实验后，小明需要把不同的化学试剂收拾归位。一共有n种化学试剂，需要放在两个盒子里，不同化学试剂放在一起可能会对盒子造成一定的损害，也可能没有损害。一个盒子里所有化学试剂对盒子的损害值等于其中损害值最大的两个化学试剂带来的损害值，损害值低于这个值的化学试剂组合的损害则会被忽略。小明希望将试剂全部放入盒中，同时希望损害值越低越好。你能告诉小明使用最优的摆放方案时，两个盒子中造成较大损害的那个值是多少么？

第一行两个整数n,m，分别表示试剂数量和m条试剂组合损害值，

其中1<=n<=200，1<=m<=500

接下来m行数据，每行3个数字a,b,c，表示第a种试剂和第b种试剂组合带来的损害值是c，数据范围1<=c<1000000。

数字间两两有空格隔开。

一行一个整数，表示两个盒子中收到较大损害的盒子的损害值。

例如——

输入：

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

输出：

3512

解释：最佳方案是23一个盒子，14一个盒子；如果234一个盒子，1一个盒子，则答案是12884。

解题思路：现场没有做出来，不知道具体考察的什么算法.但是如果要让两个盒子的最大损失值最小，最佳情况应该是两个盒子的最大损失值尽量接近，也就是应该是均衡状态。

最暴力的方法就是去遍历两个盒子的化学剂量的所有情况（时间复杂度是 $m\left( C_{n}^{0}+C_{n}^{1}+\cdots +C_{n}^{n} \right) =m\cdot 2^n$ ），这个显然不是题目想要的。

后来想的一种策略是贪心，但是无法验证是否是该问题的最优解.假设所有化学瓶的编号集合为S，最大损害值为Max，执行步骤：1. 初始状态是v1盒子装满所有的化学瓶（最大损害值为max1=Max），v2盒子没有化学瓶（最大损害值为max2=0）. 2. 遍历v1中所有的化学瓶，试着把瓶子放到v2盒子中，分别计算两个盒子的最大损害值max_new1和max_new2，挑选使得max(max_new1, max_new2)最小的瓶子编号s并且要满足max(max1, max2)>=max(max_new1, max_new2)，然后更新max1 = max_new1, max2_new2, v1盒子的化学瓶剔除s编号瓶子，v2盒子的化学瓶增加s编号瓶子. 3.重复2步骤，直到遍历v1盒子所有的瓶子都是比当前状态下最大损失值更大或者不变的情况则停止，输出max(max1, max2).

用题目给的输入例子来说明下：首先v1盒子装了1、2、3、4编号的瓶子（最大损失max1 = 28351），v2盒子没有装瓶子（最大损失max2 = 0）。

剔除v1盒子中的1编号瓶子并且装入v2盒子中， max_new1 = 12884, max_new2 = 0

剔除v1盒子中的2编号瓶子并且装入v2盒子中， max_new1 = 12884, max_new2 = 0

剔除3编号，max_new1 = 28351， max_new2 = 0

剔除4编号，max_new1 = 28351， max_new2 = 0

满足max(max_new1, max_new2)<max(max1, max2)有1号和2号瓶子，挑选max(max_new1, max_new2)最小的瓶子编号（因为1先选出来），那就是1号瓶子. 1号放入v2盒子， max1 = max_new1=12884, max2 = max_new2=0，此时v1盒子有2/3/4编号瓶子，v2盒子有1编号瓶子。

剔除v1盒子中的2编号瓶子并且装入v2盒子中， max_new1 = 12884, max_new2 = 28351

剔除3编号，max_new1 = 1805， max_new2 = 6618

剔除4编号，max_new1 = 3512， max_new2 = 2534

满足max(max_new1, max_new2)<max(max1, max2)有3号和4号瓶子编号，挑选max(max_new1, max_new2)最小的瓶子编号，那就是4号瓶子. 4号放入v2盒子， max1 = max_new1=3512, max2 = max_new2=2534，此时v1盒子有2/3编号瓶子，v2盒子有1/4编号瓶子。

剔除v1盒子中的2编号瓶子并且装入v2盒子中， max_new1 = 0, max_new2 = 28351

剔除3编号，max_new1 = 0， max_new2 = 12884

所有情况都不满足max(max_new1, max_new2)<max(max1, max2)，所以v1盒子装2/3瓶子，v2盒子装1/4瓶子是最佳平衡状态，输出max(max1, max2) = 3512。

----这题现场没做出来，我不确定对不对。

C++代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
#include "stdio.h"
using namespace std;
vector<int> vertex;//存储真实化学编号
vector<int> ver1, ver2; //分别存储v1盒子和v2盒子中化学编号数
int arc[205][205];//存储化学剂量之间的损失
int max1, max2; //全部化学瓶放在一起的最大损失值
int CountMin(vector<int> v1, vector<int> v2){
    bool flag = true;
    int max_new1 = -1, max_new2 = -1;
    while(flag){
        vector<int> ver1_temp, ver2_temp;
        int ibest = -1;
        for(int i = 0; i < v1.size(); i++){
            if(v1[i] == -1234526) continue;
            max_new1 = -1, max_new2 = -1;
            int s = v1[i];
            int j;
            for(j = 0; j < vertex.size(); j++){
                if(s == vertex[j]) break;
            }
            v1[j] = -1234526; //v1剔除
            v2[j] = s; //v2添加
            for(int k1 = 0; k1 < v1.size(); k1++){
                for(int k2 = 0; k2 < v1.size(); k2++){
                    if(v1[k1] != -1234526 && v1[k2] != -1234526){
                        if(arc[k1][k2] > max_new1)
                            max_new1 = arc[k1][k2];
                    }
                }
            }
            for(int k1 = 0; k1 < v2.size(); k1++){
                for(int k2 = 0; k2 < v2.size(); k2++){
                    if(v2[k1] != -1234526 && v2[k2] != -1234526){
                        if(arc[k1][k2] > max_new2)
                            max_new2 = arc[k1][k2];
                    }
                }
            }
            if(max(max_new1, max_new2) < max(max1, max2)){
                ibest = i;
                max1 = max_new1;
                max2 = max_new2;
                ver1 = v1;
                ver2 = v2;
            }
            v1[j] = s; //还原回去
            v2[j] = -1234526;     
        }
        if(ibest != -1){v1 = ver1; v2 = ver2;}
        else flag = false;
    }
    return max(max1, max2);
}
int main(){
    int n, m;//n为计量数，m为剂量组合数
    int a, b, c;
    int ans;
    while(cin >> n >> m){
        vertex.clear(); ver1.clear(); ver2.clear();
        max1 = -1; max2 = 0;
        memset(arc, 0, sizeof(arc));
        for(int i = 1; i <= m; i++){
            cin >> a >> b >> c;
            int j = 0, k = 0;
            for(j = 0; j < vertex.size(); j++){
                if(vertex[j] == a) break;
            }
            if(j == vertex.size()){//a不在化学编号集合中
                vertex.push_back(a);
            }
            for(k = 0; k < vertex.size(); k++){
                if(vertex[k] == b) break;
            }
            if(k == vertex.size()){//b不在化学编号集合中
                vertex.push_back(b);
            }
            arc[j][k] = c; arc[k][j] = c;
            if(c > max1) max1 = c;
        }
        ver1 = vertex;
        for(int i = 0; i < ver1.size(); i++) ver2.push_back(-1234526);
        ans = CountMin(ver1, ver2);
        cout << ans << endl;
    }
    return 0;
}

编程题二（20分）

问题描述：

你的朋友向你介绍了一款游戏叫《机器人大战》。

游戏开局会自动生成一个n行m列的矩阵，视作游戏地图，一些位置上有敌人设置的炮塔。你的任务是摧毁敌人所有的炮塔。幸运的是，这些炮塔之间的联系早已被切断，即摧毁一个炮塔不会影响其他炮塔的行动。
由于你才开始游玩该游戏，所以你手上只有一个机器人。你需要派出该机器人到矩阵任意空地。目前该机器人只有一种攻击方式：开火。每次开火会摧毁该机器人面向方向的第一个炮塔。消灭之后，该地变为空地。
由于紧急指令，机器人可能会未消灭完所有的炮塔之后被立即召回。现在，你需要记录下你的所有行动指令并交给指挥官，指挥官才能够分析地图上的局势如何。
第一行两个空格隔开的正整数n,m；
接下来一个n行m列的矩阵aij，表示地图的局势。aij=0表示该地为空地，aij=1表示该地有一炮塔。
接下来一行为sx，sy，sc，其中（sx，sy）表示机器人初始位置，sc表示机器人初始朝向，空格隔开。
最后一行一个字符串，字符串仅包含“WASDwasdZ”九种字符，其中：
W表示机器人从(i,j)走向(i-1,j)，即往上走；
A表示机器人从(i,j)走向(i,j-1)，即往左走；
S表示机器人从(i,j)走向(i+1,j)，即往下走；
D表示机器人从(i,j)走向(i,j+1)，即往右走;
其中，如果走向的下一步越过矩阵边界或者为炮塔，则你的程序需要忽略该指令。另外，执行上述指令时机器人的朝向不变。
w表示改变机器人的朝向为上；
a表示改变机器人的朝向为左；
s表示改变机器人的朝向为下；
d表示改变机器人的朝向为右；
Z表示开火。

2≤n，m≤400，1≤sx≤n，1≤sy≤m,sc∈{'w','a','s'1'd'},1≤指令长度≤103，aij∈{0,1}
输出一个n行m列的矩阵，表示执行完所有指令后的矩阵。同一行中不输出任何空格。

例如——

输入：

5 5
00100
11000
00101
11001
00111
2 3 w
ZsZSZdZ

输出：

00000
11000
00000
11001
00011

解释：设*表示机器人所在位置，则矩阵变化如下：
00100 00000 00000 00000 00000 00000
11*00 11*00 11*00 11000 11000 11000
00101->00101 -> 00001 -> 00*01 -> 00*01 -> 00*00
11001 11001 11001 11001 11001 11001
00111 00111 00111 00111 00011 00011

解题思路：这题就是一道指令识别问题，用全局变量dir来记录当前机器人的方向，cur来记录机器人下一步行动指令，然后去一个个去识别指令进行相应的操作就行.

C++代码如下：

#include<iostream>
#include<cstring>
#include<cmath>
#include "stdio.h"
using namespace std;
char arr[405][405];
int n, m;//n行m列
string dir;//机器人当前朝向
int sx, sy; //机器人起点点位置
void changeArr(string c){
    int tx, ty;
    if(c == "Z"){//开火
        if(dir == "w"){tx = sx-1; ty = sy; while(arr[tx][ty] == '0' && tx > 0){tx--;}}
        if(dir == "a"){tx = sx; ty = sy-1; while(arr[tx][ty] == '0' && ty > 0){ty--;}}
        if(dir == "s"){tx = sx+1; ty = sy; while(arr[tx][ty] == '0' && tx <= n){tx++;}}
        if(dir == "d"){tx = sx; ty = sy+1; while(arr[tx][ty] == '0' && ty <= m){ty++;}}    
        if(tx < 1 || tx > n || ty < 1 || ty > m){}
        else{arr[tx][ty] = '0';}    
    }
    if(c == "W"){//向上走
        tx = sx-1; ty = sy;
        if(tx < 1 || tx > n || ty < 1 || ty > m || arr[tx][ty] == '1'){}
        else{sx = tx; sy = ty;}    
    }
    if(c == "A"){//向左走
        tx = sx; ty = sy-1;
        if(tx < 1 || tx > n || ty < 1 || ty > m || arr[tx][ty] == '1'){}
        else{sx = tx; sy = ty;}
    }
    if(c == "S"){//向下走
        tx = sx+1; ty = sy;
        if(tx < 1 || tx > n || ty < 1 || ty > m || arr[tx][ty] == '1'){}
        else{sx = tx; sy = ty;}        
    }
    if(c == "D"){//向右走
        tx = sx; ty = sy+1;
        if(tx < 1 || tx > n || ty < 1 || ty > m || arr[tx][ty] == '1'){}
        else{sx = tx; sy = ty;} 
    }
    if(c == "w"){dir = "w";}//朝向为上
    if(c == "a"){dir = "a";}//左
    if(c == "s"){dir = "s";}//下
    if(c == "d"){dir = "d";}//右
}
int main(){
    string cur; //机器人下一步行动指令
    string s; //指令集合
    while(cin >> n >> m){
        memset(arr, 0, sizeof(arr));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++)
                cin >> arr[i][j];
        }
        cin >> sx >> sy;
        cin >> dir;
        cin >> s;
        for(int i = 0; i < s.length(); i++){
            cur = s[i];
            changeArr(cur);
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++)
                cout << arr[i][j];
            cout << endl;
        }        
    }
    return 0;
}