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

2023-11-17

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

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

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

数据范围:, 进阶:时间复杂度,空间复杂度

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin >> n;
    int x , y;
    cin >> x >> y;
    vector<int>scores;
    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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int>nums;
    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;
}

12个用例通过5个,我直接模拟的,不知道哪出问题了

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

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

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

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

/*
1
5
01102
6
MFMMFF
*/
#include <iostream>
#include <vector>
#include <algorithm>
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<<endl;
                       break;
                   }else if(desk[j] == '0'){
                       left_desk = min(left_desk,j);
                   }
               }
               if(flag == 0 && left_desk != 6){
                   desk[left_desk] = 1;
                   flag = 0;
                   cout << left_desk+1 <<endl;
               } 
           }else{
               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<<endl;
                       break;
                   }else if(desk[j] == '1'){
                       left_desk = min(left_desk,j);
                   }
               }
               if(flag == 0 && left_desk != 6){
                   desk[left_desk] = 2;
                   flag = 0;
                   cout << left_desk+1 <<endl;
               }
           }
       }
    }
}

正确答案及思路:

使用三个小根堆,分别存储当前人数为0,1,2的三种桌子的桌号,记为pq0,pq1,pq2

以男职员为例:

先尝试坐人数为1的桌子,该桌子人数就变成了2,等价于:将pq1的堆顶弹出,同时推入pq2
如果没有人数为1的桌子了,等价于pq1为空,就去坐人数为0的桌子,等价于:将pq0的堆顶弹出,同时推入pq1
因为桌号存储在优先队列,所以堆顶的桌号总是最小的,保证每个人有多个选择时优先坐最左边的桌子。

女职员同理。

时间复杂度:O(MLogN)

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <functional>
#include <cstdlib>
#include <vector>
#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t, n, m;
    string d;
    string p;
    cin >> t;
    while (t--)
    {
        cin >> n >> d >> m >> p;
        
        // 优先级队列(小根堆)
        priority_queue<int,vector<int>,greater<int>> 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 <iostream>

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;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

牛客网:美团2021校招笔试-编程题(通用编程试题,第10场) 的相关文章

  • WPF DataGrid 多选

    我读过几篇关于这个主题的文章 但很多都是来自 VS 或框架的早期版本 我想做的是从 dataGrid 中选择多行并将这些行返回到绑定的可观察集合中 我尝试创建一个属性 类型 并将其添加到可观察集合中 它适用于单个记录 但代码永远不会触发多个
  • 没有特殊字符的密码验证器

    我是 RegEx 的新手 已经进行了大量搜索 但没有找到任何具体内容 我正在编写一个验证密码字符串的正则表达式 可接受的字符串必须至少具有 4 种字符类型中的 3 种 数字 小写字母 大写字母 特殊字符 我对包含有一个想法 也就是说 如果这
  • 根据属性的类型使用文本框或复选框

    如果我有这样的结构 public class Parent public string Name get set public List
  • 类型中的属性名称必须是唯一的

    我正在使用 Entity Framework 5 并且有以下实体 public class User public Int32 Id get set public String Username get set public virtual
  • C++11 删除重写方法

    Preface 这是一个关于最佳实践的问题 涉及 C 11 中引入的删除运算符的新含义 当应用于覆盖继承父类的虚拟方法的子类时 背景 根据标准 引用的第一个用例是明确禁止调用某些类型的函数 否则转换将是隐式的 例如最新版本第 8 4 3 节
  • 传递给函数时多维数组的指针类型是什么? [复制]

    这个问题在这里已经有答案了 我在大学课堂上学习了 C 语言和指针 除了多维数组和指针之间的相似性之外 我认为我已经很好地掌握了这个概念 我认为由于所有数组 甚至多维 都存储在连续内存中 因此您可以安全地将其转换为int 假设给定的数组是in
  • 如何从本机 C(++) DLL 调用 .NET (C#) 代码?

    我有一个 C app exe 和一个 C my dll my dll NET 项目链接到本机 C DLL mynat dll 外部 C DLL 接口 并且从 C 调用 C DLL 可以正常工作 通过使用 DllImport mynat dl
  • 如何连接重叠的圆圈?

    我想在视觉上连接两个重叠的圆圈 以便 becomes 我已经有部分圆的方法 但现在我需要知道每个圆的重叠角度有多大 但我不知道该怎么做 有人有主意吗 Phi ArcTan Sqrt 4 R 2 d 2 d HTH Edit 对于两个不同的半
  • 如何在 C++ 中标记字符串?

    Java有一个方便的分割方法 String str The quick brown fox String results str split 在 C 中是否有一种简单的方法可以做到这一点 The 增强分词器 http www boost o
  • C# - 当代表执行异步任务时,我仍然需要 System.Threading 吗?

    由于我可以使用委托执行异步操作 我怀疑在我的应用程序中使用 System Threading 的机会很小 是否存在我无法避免 System Threading 的基本情况 只是我正处于学习阶段 例子 class Program public
  • 空指针与 int 等价

    Bjarne 在 C 编程语言 中写道 空指针与整数零不同 但 0 可以用作空指针的指针初始值设定项 这是否意味着 void voidPointer 0 int zero 0 int castPointer reinterpret cast
  • LINQ:使用 INNER JOIN、Group 和 SUM

    我正在尝试使用 LINQ 执行以下 SQL 最接近的是执行交叉联接和总和计算 我知道必须有更好的方法来编写它 所以我向堆栈团队寻求帮助 SELECT T1 Column1 T1 Column2 SUM T3 Column1 AS Amoun
  • 如何在 Linq to SQL 中使用distinct 和 group by

    我正在尝试将以下 sql 转换为 Linq 2 SQL select groupId count distinct userId from processroundissueinstance group by groupId 这是我的代码
  • C 函数 time() 如何处理秒的小数部分?

    The time 函数将返回自 1970 年以来的秒数 我想知道它如何对返回的秒数进行舍入 例如 对于100 4s 它会返回100还是101 有明确的定义吗 ISO C标准没有说太多 它只说time 回报 该实现对当前日历时间的最佳近似 结
  • 有没有办法让 doxygen 自动处理未记录的 C 代码?

    通常它会忽略未记录的 C 文件 但我想测试 Callgraph 功能 例如 您知道在不更改 C 文件的情况下解决此问题的方法吗 设置变量EXTRACT ALL YES在你的 Doxyfile 中
  • 为什么 std::uint32_t 与 uint32_t 不同?

    我对 C 有点陌生 我有一个编码作业 很多文件已经完成 但我注意到 VS2012 似乎有以下语句的问题 typedef std uint32 t identifier 不过 似乎将其更改为 typedef uint32 t identifi
  • DotNetZip:如何提取文件,但忽略zip文件中的路径?

    尝试将文件提取到给定文件夹 忽略 zip 文件中的路径 但似乎没有办法 考虑到其中实现的所有其他好东西 这似乎是一个相当基本的要求 我缺少什么 代码是 using Ionic Zip ZipFile zf Ionic Zip ZipFile
  • MySQL Connector C/C API - 使用特殊字符进行查询

    我是一个 C 程序 我有一个接受域名参数的函数 void db domains query char name 使用 mysql query 我测试数据库中是否存在域名 如果不是这种情况 我插入新域名 char query 400 spri
  • 指针和内存范围

    我已经用 C 语言编程有一段时间了 但对 C 语言还是很陌生 有时我对 C 处理内存的方式感到困惑 考虑以下有效的 C 代码片段 const char string void where is this pointer variable l
  • 类型或命名空间“MyNamespace”不存在等

    我有通常的类型或命名空间名称不存在错误 除了我引用了程序集 using 语句没有显示为不正确 并且我引用的类是公共的 事实上 我在不同的解决方案中引用并使用相同的程序集来执行相同的操作 并且效果很好 顺便说一句 这是VS2010 有人有什么

随机推荐