有个网站整理了六十多道德科面试一星题 可以看看 大概率能碰到原题
不知道是哪位爷的博客 引用一下啦
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) 回帖