美团2021笔试通用卷09

01 - [编程题]淘汰分数

某比赛已经进入了淘汰赛阶段,已知共有n名选手参与了此阶段比赛，他们的得分分别是a_1,a_2….a_n,小美作为比赛的裁判希望设定一个分数线m，使得所有分数大于m的选手晋级，其他人淘汰。 但是为了保护粉丝脆弱的心脏，小美希望晋级和淘汰的人数均在[x,y]之间。 显然这个m有可能是不存在的，也有可能存在多个m，如果不存在，请你输出-1，如果存在多个，请你输出符合条件的最低的分数线。

输入描述:

输入第一行仅包含三个正整数n,x,y，分别表示参赛的人数和晋级淘汰人数区间。(1<=n<=50000,1<=x,y<=n) 输入第二行包含n个整数，中间用空格隔开，表示从1号选手到n号选手的成绩。(1<=|a_i|<=1000)

输出描述:

输出仅包含一个整数，如果不存在这样的m，则输出-1，否则输出符合条件的最小的值。

输入例子1:

6 2 3 1 2 3 4 5 6

输出例子1:

3

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 50050;
int scores[N];
int main()
{
    int n, x, y;
    
    scanf("%d%d%d", &n, &x, &y);
    for(int i = 0; i < n; i++)
        scanf("%d", scores + i);
    sort(scores, scores + n);
    if(2 * x > n) puts("-1");
    else{
        int m = scores[x - 1], i = x - 1;
        while(i < n && scores[i] == m) i++;
        if(n - i>= x && n - i <= y) printf("%d\n", m);
        else puts("-1");
    }
    return 0;
}

02 - [编程题]正则序列

我们称一个长度为n的序列为正则序列，当且仅当该序列是一个由1~n组成的排列，即该序列由n个正整数组成，取值在[1,n]范围，且不存在重复的数，同时正则序列不要求排序 有一天小团得到了一个长度为n的任意序列，他需要在有限次操作内，将这个序列变成一个正则序列，每次操作他可以任选序列中的一个数字，并将该数字加一或者减一。 请问他最少用多少次操作可以把这个序列变成正则序列？

输入描述:

输入第一行仅包含一个正整数n，表示任意序列的长度。(1<=n<=20000) 输入第二行包含n个整数，表示给出的序列，每个数的绝对值都小于10000。

输出描述:

输出仅包含一个整数，表示最少的操作数量。

输入例子1:

5 -1 2 3 10 100

输出例子1:

103

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 20020;

int n;
int a[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
       cin >> a[i];
    sort(a + 1, a + n + 1);
    int res = 0;
    for(int i = 1; i <= n; i++)
        res += abs(a[i] - i);
    cout << res << endl;
    return 0;
}

03 - [编程题]公司食堂

小美和小团所在公司的食堂有N张餐桌，从左到右摆成一排，每张餐桌有2张餐椅供至多2人用餐，公司职员排队进入食堂用餐。小美发现职员用餐的一个规律并告诉小团：当男职员进入食堂时，他会优先选择已经坐有1人的餐桌用餐，只有当每张餐桌要么空着要么坐满2人时，他才会考虑空着的餐桌； 当女职员进入食堂时，她会优先选择未坐人的餐桌用餐，只有当每张餐桌都坐有至少1人时，她才会考虑已经坐有1人的餐桌； 无论男女，当有多张餐桌供职员选择时，他会选择最靠左的餐桌用餐。现在食堂内已有若干人在用餐，另外M个人正排队进入食堂，小团会根据小美告诉他的规律预测排队的每个人分别会坐哪张餐桌。

输入描述:

第一行输入一个整数T（1<=T<=10），表示数据组数。 每组数据占四行，第一行输入一个整数N（1<=N<=500000）； 第二行输入一个长度为N且仅包含数字0、1、2的字符串，第i个数字表示左起第i张餐桌已坐有的用餐人数； 第三行输入一个整数M（1<=M<=2N且保证排队的每个人进入食堂时都有可供选择的餐桌）； 第四行输入一个长度为M且仅包含字母M、F的字符串，若第i个字母为M，则排在第i的人为男性，否则其为女性。

输出描述:

每组数据输出占M行，第i行输出一个整数j（1<=j<=N），表示排在第i的人将选择左起第j张餐桌用餐。

输入例子1:

1 5 01102 6 MFMMFF

输出例子1:

2 1 1 3 4 4

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 500050;

int T, n, m;
char s[N], gender[2 * N];
int a[N];

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        scanf("%s", s);
        scanf("%d", &m);
        scanf("%s", gender);
        priority_queue<int, vector<int>, greater<int>> q0, q1; 
        
        for(int i = 1; i <= n; i++)
        {
            a[i] = s[i - 1] - '0';
            if(a[i] == 0) q0.push(i);
            else if(a[i] == 1) q1.push(i);
        }
        // 处理查询
        for(int i = 0; i < m; i++)
        {
            if(gender[i] == 'M')
            {
                if(!q1.empty())
                {
                    int t = q1.top();
                    q1.pop();
                    printf("%d\n", t);
                }
                else{
                    int t = q0.top();
                    q0.pop();
                    q1.push(t);
                    printf("%d\n", t);
                }
            }
            else{
                if(!q0.empty())
                {
                    int t = q0.top();
                    q0.pop();
                    q1.push(t);
                    printf("%d\n", t);
                }
                else{
                    int t = q1.top();
                    q1.pop();
                    printf("%d\n", t);
                }
            }
        }
    }
    return 0;
}

04 - [编程题]最优二叉树II

小团有一个由N个节点组成的二叉树，每个节点有一个权值。定义二叉树每条边的开销为其两端节点权值的乘积，二叉树的总开销即每条边的开销之和。小团按照二叉树的中序遍历依次记录下每个节点的权值，即他记录下了N个数，第i个数表示位于中序遍历第i个位置的节点的权值。之后由于某种原因，小团遗忘了二叉树的具体结构。在所有可能的二叉树中，总开销最小的二叉树被称为最优二叉树。现在，小团请小美求出最优二叉树的总开销。

这个约等于暴力了... 能过80%的数据

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
 
using namespace std;
 
const int N = 310;
 
int n;
int a[N];
int f[N][N][N]; // 以i 为根节点 [a .. b]为中序遍历的二叉树的集合 最小值
 
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
       cin >> a[i];
    memset(f, 0x3f, sizeof f);
    for(int len = 1; len <= n; len++)
        for(int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            if(len == 1)
            {
                f[l][l][l] = 0;
                continue;
            }
            // 枚举root
            for(int root = l; root <= r; root++)
            {
               // 左边 [x][l][root - 1];
                int sl = 0x3f3f3f3f, sr = 0x3f3f3f3f;
                if(root - 1 >= l)
                    for(int x = l; x <= root - 1; x++)
                       sl = min(sl, f[x][l][root - 1] + a[x] * a[root]);
                if(root + 1 <= r)
                    for(int x = root + 1; x <= r; x++)
                        sr = min(sr, f[x][root + 1][r] + a[x] * a[root]);
                if(sl == 0x3f3f3f3f) sl = 0;
                if(sr == 0x3f3f3f3f) sr = 0;
                f[root][l][r] = sl + sr;
            }
        }
    int ans = 0x3f3f3f3f;
    for(int i = 1; i <= n; i++)
        ans = min(ans, f[i][1][n]);
    cout << ans << endl;
    return 0;
}

学一下AC的代码吧hh 记忆化搜索真的很少写了 虽然感觉复杂度是一样的

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int num[305];
int dp[305][305][305];
int dfs(int l,int r,int f)
{
    if (l>r)
        return 0;
    if(dp[l][r][f]!=-1)
        return dp[l][r][f];
    int res=inf;
    for(int i=l;i<=r;i++)
    {
        int left=dfs(l,i-1,i);
        int right=dfs(i+1,r,i);
        res=min(res,left+right+num[i]*num[f]);
    }
    dp[l][r][f]=res;
    return dp[l][r][f];
}
int main()
{
    memset(dp,-1,sizeof(dp));
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
    }
    cout<<dfs(1,n,0)<<endl;
}