顺丰科技2021-11-21笔试

运筹优化算法岗位.

选择题（20*3分）：（包含了单选和多选），考察的内容包括NP问题和P问题、运筹学基本内容（主考线性规划、最短路径算法、动态规划、分支定界等）、数据结构基础知识、python编程基础.

简答题（2*20分）：

第一题是写一下单纯形算法流程.

第二题是写一下从初始点s到终止点t的Dijkstra算法流程.

编程题（2*20分）：

编程题一：

完美平均
时间限制： 1000MS
内存限制： 65536KB
题目描述：
对于一个整数数组，如果其中所有数字的平均值是1，那么就称其为完美平均。现在给定一个数组，你可以往里面添加任意多个非负整数，目标是让其最终变成一个完美平均的数组。可以证明一定存在一个方案达到这样的目标。希望你算出最少需要添加多少个非负整数，可以让这个数组变成完美平均的。
输入描述
第一行一个整数n，1<=n<=100
第二行n个整数，其中任意一个数大小范围是[-10000,10000]。
输出描述
一个整数，表示最少需要添加多少个非负整数。
样例输入
3
1 1 1
样例输出
0
提示
补充样例2：
输入：
3
1 2 3
输出：
3

求解思路：这道题还是很容易的，数组平均值为1说明——“数组的和=数组的元素个数”.

先计算当前数组的和s，元素的个数sz. 用ans来表示最少添加的非负整数的个数.

分类(s = sz, s > sz , 0< s < sz, s < 0 < sz)去讨论下

1. s = sz, 那就是不用添加了，ans = 0.

2. s > sz, 用贪心的思想去想，要想让“数组的和=数组的元素个数”快速成立，那肯定是加0. 那添加了几个0呢，是s - sz个. 所以 ans = s - sz.

3.0<s<sz，根据题目给的原来数组长度是<=100的，所以sz<=100，所以只要添加一个元素就可以达到“数组的和=数组的元素个数”（添加的那个元素值为sz+1-s）.所以ans=1.

4.s<0<sz，要达到“数组的和=数组的元素个数”这个目标，可以每次都尝试添加最大的元素值(10000)，直到sz - s <= 10000，此时添加sz - s就可以了.

#include<iostream>
#include<vector>
#include "stdio.h"
using namespace std;
int main(){
    int n, t, ans, sz;
    while(cin >> n){
        vector<int> A;
        ans = 0;
        int s = 0;
        for(int i = 0; i < n; i++){
            cin >> t;
            s += t;
            A.push_back(t);
        }
        sz = A.size();
        if(s >= sz){
            ans = s - sz;
        }
        else if(s > 0){//和小于个数并且和是大于0
            ans = 1;
        }
        else{//和小于个数并且和是小于0的.
            sz = sz + 1;
            int gap = sz - s; //加一个数看看情况
            ans ++;
            if(gap <= 10000){}
            //每次加10000
            else{
                while(gap > 10000){
                    sz = sz + 1;
                    s = s + 10000;
                    gap = sz - s;
                    ans ++;
                    if(gap <= 10000) break;
                }
            }

        }        
        cout << ans << endl;
    }
    return 0;
}

编程题二：

挑选关卡
时间限制： 1000MS
内存限制： 65536KB
题目描述：
小明正在玩一款闯关的游戏，小明将按顺序依次面对不同的关卡，每个关卡都有一个难度值。小明可以选择参与或者不参与该关卡，如果参与那么他可以获得该关卡难度值等值的积分，如果不参与那么就可以直接跳过进入下一关的选择。但是该游戏有一个限制，就是小明想参与的关卡的难度必须高于之前参与过的关卡的难度，第一关难度不做限制。现在按顺序告诉你所有关卡的难度值，你能算出小明最多可以得到多少积分吗？
输入描述
第一行一个整数n，表示关卡的总数量，1<=n<=3000
第二行n个整数，从左到右是关卡的顺序，数字大小表示关卡难度，任意数字大小范围是[1,1000000000]。
输出描述
一个整数，表示小明最多可以得到多少积分。
样例输入
3
1 3 2
样例输出
4
提示
解释：参与1，3
补充样例2：
输入：
3
3 3 3
输出：
3
补充样例3：
输入：
4
1 3 2 4
输出：
8
解释：参与1，3，4

求解思路：不知道哪里错了（没全对），我想的是用动态规划来进行求解，difnum[i]:第i个关卡的积分值，Maxnum[i]：表示以第i个关卡结尾的最大积分数.

动态转移方程应该很简单能写出来~Maxnum[i] = { max_{j : 0 ~ i-1}(Maxnum[j] + difnum[i] : difnum[i] > difnum[j]).

最大积分数 = max_{j : 0 ~ n-1}(Maxnum[j]).

#include<iostream>
#include<vector>
#include<cstring>
#include "stdio.h"
using namespace std;
int main(){
    int n;
    long long Maxnum[3005];//Maxnum[i]-以i为结尾的最大积分数
    while(cin >> n){
        vector<int> difnum(n);
        memset(Maxnum, 0, sizeof(Maxnum));
        for(int i = 0; i < n; i++)
            cin >> difnum[i];
        int i, j;
        Maxnum[0] = difnum[0]; 
        for(int i = 0; i < n; i++)
            Maxnum[i] = difnum[i];
        for(i = 1; i < n; i++){
            int flag = false;
            for(j = 0; j < i; j++){
                if((difnum[i] > difnum[j]) && (Maxnum[i] < difnum[i] + Maxnum[j])){
                    Maxnum[i] = difnum[i] + Maxnum[j];
                    flag = true;
                }
            }
            if(!flag) Maxnum[i] = difnum[i];
        }
        long long s = -1;
        for(i = 0; i < n; i++){
            if(Maxnum[i] > s)
                s = Maxnum[i];
        }
        cout << s << endl;
    }
    return 0;
}

#笔试题目##秋招#