首页 > 华为OD社招 C++ 编程笔试
头像
穷人的代表
编辑于 2021-07-17 18:25
+ 关注

华为OD社招 C++ 编程笔试

有个网站整理了六十多道德科面试一星题 可以看看 大概率能碰到原题
不知道是哪位爷的博客 引用一下啦

1星:
1 停车位问题
有一横排车位,有至少一个车位停了车,也至少有一个车位没停车。一个车位有车用1表示,无车用0表示。为了避免剐蹭,请为司机规划停在哪个车位,距离其他车中间间隔的车位最远。输入:一组数据,代表目前车位的状态。 输出:当前车辆停车距离其他车辆的最大间距
栗子:
输入
1 0 0 0 1 0 1 0 1 0
输出
2
这个题比较简单,用1分割输入的数据,再考虑首尾为0的情况,取最大值即可

示例程序(不一定全对 我记不起来当时是怎么写的了 ,而且也没有测试环境)
其实连存都不用存 直接边输入边处理就好
#include <string>
#include <sstream>
#include <iostream>
#include <vector>

int parking(std::vector<int>& park) {
    std::vector<int>index;
    for (int i = 0; i < park.size(); i++) {
        if (park[i] == 1)
            index.push_back(i);
    }
    //停车场没车
    if (index.size() == 0)
        return park.size() - 1;

    int res = 0;

    //如果最左边或者最右边没停车
    int leftside = 0;
    int rightside = park.size()-1;
    if (index[0] != 0 || index[index.size() - 1] != rightside) {
        res = std::max(index[0], rightside - index[index.size() - 1]);
    }
        
    for (int i = 1; i < index.size(); i++) {
        res = std::max(res, (index[i] - index[i - 1]) / 2);
    }
    return res;
}
int main(int argc,char** argv) {
    std::string s;
    while (std::getline(std::cin, s)) {
        std::stringstream ss(s);
        int n;
        std::vector<int>park;
        while (ss >> n) {
            park.push_back(n);
        }
        std::cout << parking(park) << std::endl;
    }
    return 0;
}


简单测试
1 0 0 0 1 0 1 0 1 0
2
1 0 0 0 0 0 0 0 0 0
9
1 0 0 0
3
0 0 0 1
3
0 0 0 0 0 0 0 0 0 1
9
1 0 0 0 0 0 0 0 0 1
4
0 0 0 0 0 0 0 0 0 0
9
0 0 0
2

2 组队问题
给定一些人和他们的能力值,以及组成一个队伍所需的最小能力值要求,每个人只能组一次队伍,每个队伍只能由一个人或者两个人组成 ,求能组成的最多的队伍数
输入 :
人数 数量级500万
能力值
组队最小能力值
栗子:
输入
5
1 3 5 7 9
8
输出
3
解释:1 7组队 3 5组队 9单独组队
比较简单,对输入数据排序,先将单独组队的拎出来,再从能力不足的人里面将相对能力较大的人先组队(能力大的人带能力小的人) AC 90%  对于输入全为1的情况没做特殊处理导致超时
这是一道简化了的贪心 原题是人数不固定 那个相对更难一些

2 星 用最小的补贴使得1号店家成为最受欢迎的店家
美食节到了 商家举行投票活动,有n个市民参加投票,1号商家可以采用补贴的形式让市民改投自己,求1号商家用最少的补贴成为最受欢迎的商家 如果1号已经是最受欢迎的返回0,否则返回所需的补贴
栗子:
输入:
想投的店家 改投所需的补贴
5
2 10
3 20
4 30
5 40
5 90    
输出
50
解释 将原来想投2号的和想投5号的给予补贴 10+40使其改投1号  此时一号得票为两票 最受欢迎

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int main(int argc, char** argv)
{
    //首先读入所有的数据,使用一个二维数组,记录所有商家的票数,按照代价从大到小排序,
    //用数组模拟栈,方便从尾后弹出
    //我的思路,1号商家的票数想要成为最高,首先得和当前票数最高的商家一样高
    //所以使用一个优先级队列,记录当前票数最高的商家,不停地减小最高的商家,
    //然后弹出它代价最小的票数(这个是必须要加的)
    //当没有商家比一号商家更高的时候,从所有代价最小的里面选出一个就好了
    int n;
    while (cin >> n) {
        int aa, bb;
        char c;
        vector<vector<int>>nums(n);
        for (int i = 0; i < n; i++)
        {
            cin >> aa>> c >> bb;
            nums[aa - 1].push_back(bb);
        }
        for (int i = 0; i < n; i++)
            sort(nums[i].begin(), nums[i].end(), greater<int>());
        int cur = nums[0].size();
        auto cmp = [](pair<int, int>& a, pair<int, int>& b) {
            return a.second < b.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)>q(cmp);
        for (int i = 1; i < n; i++)
            if (nums[i].size())
                q.push({ i,nums[i].size() });
        int ret = 0;
        while (q.top().second > cur)
        {
            auto t = q.top();
            q.pop();
            cur++;
            ret += nums[t.first].back();
            nums[t.first].pop_back();
            if (t.second > 1)
                q.push({ t.first,t.second - 1 });
        }
        int min_ = INT_MAX;
        for (int i = 0; i < nums.size(); i++)
            if (nums[i].size())
                min_ = min(min_, nums[i].back());
        cout << ret + min_;
    }
    return 0;
}



全部评论

(7) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐