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

有个网站整理了六十多道德科面试一星题可以看看大概率能碰到原题

不知道是哪位爷的博客引用一下啦

http://www.amoscloud.com/?cat=57

1星：

1 停车位问题

有一横排车位，有至少一个车位停了车，也至少有一个车位没停车。一个车位有车用1表示，无车用0表示。为了避免剐蹭，请为司机规划停在哪个车位，距离其他车中间间隔的车位最远。输入：一组数据，代表目前车位的状态。输出：当前车辆停车距离其他车辆的最大间距

栗子：

输入

1 0 0 0 1 0 1 0 1 0

输出

这个题比较简单，用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

输出

解释：1 7组队 3 5组队 9单独组队

比较简单，对输入数据排序，先将单独组队的拎出来，再从能力不足的人里面将相对能力较大的人先组队（能力大的人带能力小的人） AC 90% 对于输入全为1的情况没做特殊处理导致超时

这是一道简化了的贪心原题是人数不固定那个相对更难一些

2 星用最小的补贴使得1号店家成为最受欢迎的店家

美食节到了商家举行投票活动，有n个市民参加投票，1号商家可以采用补贴的形式让市民改投自己，求1号商家用最少的补贴成为最受欢迎的商家如果1号已经是最受欢迎的返回0，否则返回所需的补贴

栗子：

输入：

想投的店家改投所需的补贴

输出

解释将原来想投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;
}

#笔经##华为#