牛客网：美团2021校招笔试-编程题(通用编程试题,第10场）

某比赛已经进入了淘汰赛阶段,已知共有n名选手参与了此阶段比赛，他们的得分分别是a_1,a_2….a_n,小美作为比赛的裁判希望设定一个分数线m，使得所有分数大于m的选手晋级，其他人淘汰。

但是为了保护粉丝脆弱的心脏，小美希望晋级和淘汰的人数均在[x,y]之间。

显然这个m有可能是不存在的，也有可能存在多个m，如果不存在，请你输出-1，如果存在多个，请你输出符合条件的最低的分数线。

数据范围：， 进阶：时间复杂度，空间复杂度

#include 
#include 
#include 
using namespace std;
int main(){
    int n;
    cin >> n;
    int x , y;
    cin >> x >> y;
    vectorscores;
    for(int i = 0;i < n;i++){
        int score;
        cin >> score;
        scores.push_back(score);
    }
    //dataaccess
    sort(scores.begin(),scores.end());
    for(int i = 0;i < n; i++){
        //假设m = scores[i]

        if(x <= i+1 && i+1 <= y && n - i <= y && n - i >= x){
            cout << scores[i];
            return 0;
        }
    }
    cout << -1;
    return 0;
}

我们称一个长度为n的序列为正则序列，当且仅当该序列是一个由1~n组成的排列，即该序列由n个正整数组成，取值在[1,n]范围，且不存在重复的数，同时正则序列不要求排序

有一天小团得到了一个长度为n的任意序列s，他需要在有限次操作内，将这个序列变成一个正则序列，每次操作他可以任选序列中的一个数字，并将该数字加一或者减一。

请问他最少用多少次操作可以把这个序列变成正则序列？

数据范围：， 进阶：时间复杂度，空间复杂度

#include 
#include 
#include 
using namespace std;
int main(){
    int n;
    cin >> n;
    vectornums;
    for(int i = 0 ;i < n; i++){
        int num;
        cin >> num;
        nums.push_back(num);
    }
    sort(nums.begin(),nums.end());
    int ans = 0;
    for(int i = 0;i < n;i++){
        ans += abs(i+1 - nums[i]);
    }
    cout << ans;
    return 0;
}

小美和小团所在公司的食堂有N张餐桌，从左到右摆成一排，每张餐桌有2张餐椅供至多2人用餐，公司职员排队进入食堂用餐。小美发现职员用餐的一个规律并告诉小团：当男职员进入食堂时，他会优先选择已经坐有1人的餐桌用餐，只有当每张餐桌要么空着要么坐满2人时，他才会考虑空着的餐桌；

当女职员进入食堂时，她会优先选择未坐人的餐桌用餐，只有当每张餐桌都坐有至少1人时，她才会考虑已经坐有1人的餐桌；

无论男女，当有多张餐桌供职员选择时，他会选择最靠左的餐桌用餐。现在食堂内已有若干人在用餐，另外M个人正排队进入食堂，小团会根据小美告诉他的规律预测排队的每个人分别会坐哪张餐桌。

进阶：时间复杂度,空间复杂度

#include 
#include 
#include 
using namespace std;
int main(){
    int T;
    cin >> T;
    for(int i = 0;i < T;i++){
        //餐桌数目
        int N;
        cin >> N;
        //餐桌此时占用情况
        string desk;
        cin >> desk;
        //待入座人员人数
        int M;
        cin >> M;
         //待入座人员性别
        string gender;
        cin >> gender;
        //有m个人将要进入餐馆
       for(int k =0;k < M;k++){
           //第一种情况男性
           if(gender[k] == 'M'){
               int flag = 0;
               int left_desk = N;
               for(int j = 0;j < N;j++){
                   //已经坐有1人的餐桌用餐
                   if(desk[j] == '1'){
                       desk[j] = '2';
                       flag = 1;
                       cout << j+1<
                       left_desk = min(left_desk,j);
                   }
               }
               if(flag == 0 && left_desk != 6){
                   desk[left_desk] = 1;
                   flag = 0;
                   cout << left_desk+1 <
               int flag = 0;
               int left_desk = N;
               for(int j = 0;j < N;j++){
                   if(desk[j] == '0'){
                       flag = 1;
                       desk[j] = '1';
                       cout << j+1<
                       left_desk = min(left_desk,j);
                   }
               }
               if(flag == 0 && left_desk != 6){
                   desk[left_desk] = 2;
                   flag = 0;
                   cout << left_desk+1 < 
正确答案及思路： 
 
 
使用三个小根堆，分别存储当前人数为0,1,2的三种桌子的桌号，记为pq0,pq1,pq2
 
 
以男职员为例：
 
 
先尝试坐人数为1的桌子，该桌子人数就变成了2，等价于：将pq1的堆顶弹出，同时推入pq2
 如果没有人数为1的桌子了，等价于pq1为空，就去坐人数为0的桌子，等价于：将pq0的堆顶弹出，同时推入pq1
 因为桌号存储在优先队列，所以堆顶的桌号总是最小的，保证每个人有多个选择时优先坐最左边的桌子。
 
 
女职员同理。
 
 
时间复杂度：O(MLogN)
 
 
#include 
#include 
#include 
#include 
#include 
#include 
#include

using namespace std;

int main()
{
    int t, n, m;
    string d;
    string p;
    cin >> t;
    while (t--)
    {
        cin >> n >> d >> m >> p;
        
        // 优先级队列（小根堆）
        priority_queue,greater> zero, one;
        for (int j = 0; j < n; j++)
        {
            if (d[j] == '0')
            {
                zero.push(j + 1);
            }
            else if (d[j] == '1')
            {
                one.push(j + 1);
            }
        }
        for (int i = 0; i < m; i++)
        {
            if (p[i] == 'M')
            {
                // 如果没有仅一人的座位
                if (one.empty())
                {
                    cout << zero.top() << 'n';
                    one.push(zero.top());
                    zero.pop();
                }
                else
                {
                    cout << one.top() << 'n';
                    one.pop();
                }
            }
            else
            {
                // 如果没有空位置
                if (zero.empty())
                {
                    cout << one.top() << 'n';
                    one.pop();
                }
                else
                {
                    cout << zero.top() << 'n';
                    one.push(zero.top());
                    zero.pop();
                }
            }
        }
    }
}

 
4，没做
 
 
 
小团有一个由N个节点组成的二叉树，每个节点有一个权值。定义二叉树每条边的开销为其两端节点权值的乘积，二叉树的总开销即每条边的开销之和。小团按照二叉树的中序遍历依次记录下每个节点的权值，即他记录下了N个数，第i个数表示位于中序遍历第i个位置的节点的权值。之后由于某种原因，小团遗忘了二叉树的具体结构。在所有可能的二叉树中，总开销最小的二叉树被称为最优二叉树。现在，小团请小美求出最优二叉树的总开销。
 
 
树形dp。
 首先要明白中序遍历的特点：选取其中一个节点，其左边的节点都是其左子树上的节点，其右边的节点都是其右子树上的节点。
 动态规划三步走：明确下标意义，寻找递推公式，dp数组初始化。
 首先是dp数组的下标意义。
 我用了两个二维数组，ldp[i][j]表示以以node[j+1]为根节点、node[i]到node[j]作为左子树节点的最优二叉树的权值；rdp[i][j]表示以以node[i-1]为根节点、node[i]到node[j]作为右子树节点的最优二叉树的权值。
 其次是递推公式。
 最后是初始化
 其实也用不着初始化，在递推公式里就能完成。
 代码如下：
 
#include 

using namespace std;

int ldp[302][302]{};
int rdp[302][302]{};
int node[302]{};

void f(int a, int b) {
	int x, y;
    ldp[a][b] = rdp[a][b] = 100000000;
	for (int i = a; i <= b; ++i) {
		x = ldp[a][i - 1] + node[i] * node[b + 1] + rdp[i + 1][b];
		y = ldp[a][i - 1] + node[i] * node[a - 1] + rdp[i + 1][b];
		if (x < ldp[a][b])ldp[a][b] = x;
		if (y < rdp[a][b])rdp[a][b] = y;
	}
}

int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> node[i];
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 1; j <= N-i; ++j) {
			f(j, j + i);
		}
	}
	cout << ldp[1][N];
	return 0;
}