百度2017春招笔试真题编程题集合
一、度度熊想去商场买一顶帽子，商场里有N顶帽子，有些帽子的价格可能相同。度度熊想买一顶价格第三便宜的帽子，问第三便宜的帽子价格是多少？
输入描述:
首先输入一个正整数N（N <= 50），接下来输入N个数表示每顶帽子的价格（价格均是正整数，且小于等于1000）
输出描述:
如果存在第三便宜的帽子，请输出这个价格是多少，否则输出-1
输入例子:
10
10 10 10 10 20 20 30 30 40 40
输出例子:
30
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n = 0;
while (cin >> n)
{
vector<int> price(n, 0);
for (int i = 0; i < n; ++i)
cin >> price[i];
sort(price.begin(), price.end());
int cnt = 1;
int pos = 1;
for (; pos < price.size(); ++pos)
{
if (price[pos]>price[pos - 1])
++cnt;
if (cnt == 3)
break;
}
if (cnt == 3)
cout << price[pos] << endl;
else
cout << -1 << endl;
}
return 0;
}
二、一个数轴上共有N个点，第一个点的坐标是度度熊现在位置，第N-1个点是度度熊的家。现在他需要依次的从0号坐标走到N-1号坐标。但是除了0号坐标和N-1号坐标，他可以在其余的N-2个坐标中选出一个点，并直接将这个点忽略掉，问度度熊回家至少走多少距离？
输入描述:
输入一个正整数N, N <= 50。
接下来N个整数表示坐标，正数表示X轴的正方向，负数表示X轴的负方向。绝对值小于等于100
输出描述:
输出一个整数表示度度熊最少需要走的距离。
输入例子:
4
1 4 -1 3
输出例子:
4
#include<iostream>
#include<vector>
#include<algorithm>
#include<limits.h>
using namespace std;
int main()
{
int n = 0;
while (cin >> n)
{
vector<int> posVec(n, 0);
for (int i = 0; i < n; ++i)
cin >> posVec[i];
int minDis = INT_MAX;
for (int i = 1; i < n - 1; ++i)
{
int cnt = 0;
int pre = posVec[0];
for (int j = 1; j < n; ++j)
{
if (j != i)
{
cnt += abs(posVec[j] - pre);
pre = posVec[j];
}
}
minDis = min(minDis, cnt);
}
cout << minDis << endl;
}
return 0;
}
三、三维空间中有N个点，每个点可能是三种颜色的其中之一，三种颜色分别是红绿蓝，分别用'R', 'G', 'B'表示。 现在要找出三个点，并组成一个三角形，使得这个三角形的面积最大。但是三角形必须满足：三个点的颜色要么全部相同，要么全部不同。
输入描述:
首先输入一个正整数N三维坐标系内的点的个数.(N <= 50)
接下来N行，每一行输入 c x y z，c为'R', 'G', 'B' 的其中一个。x，y，z是该点的坐标。(坐标均是0到999之间的整数)
输出描述:
输出一个数表示最大的三角形面积，保留5位小数。
输入例子:
5
R 0 0 0
R 0 4 0
R 0 0 3
G 92 14 7
G 12 16 8
输出例子:
6.00000
#include<iostream>
#include<vector>
#include<algorithm>
#include<limits.h>
#include<iomanip>
using namespace std;
typedef struct
{
int x, y, z;
}Point;
double pointDis(Point p1, Point p2)
{
double a = pow(p1.x - p2.x, 2);
double b = pow(p1.y - p2.y, 2);
double c = pow(p1.z - p2.z, 2);
return sqrt(a + b + c);
}
double pointSize(double a, double b, double c)
{
double p = (a + b + c) / 2;
return sqrt(p*(p - a)*(p - b)*(p - c));
}
bool doubleBig(double a, double b)
{
if (a - b > 0.000001)
return true;
else
return false;
}
bool isTriangle(double a, double b, double c)
{
if (doubleBig(a + b, c) && doubleBig(a + c, b) && doubleBig(c + b, a))
return true;
else
return false;
}
double pointSizeOne(vector<Point> pointPos)
{
double maxSize = INT_MIN;
for (int i = 0; i < (int)pointPos.size() - 2; ++i)
{
for (int j = i + 1; j < (int)pointPos.size() - 1; ++j)
{
for (int k = j + 1; k < pointPos.size(); ++k)
{
double a = pointDis(pointPos[i], pointPos[j]);
double b = pointDis(pointPos[i], pointPos[k]);
double c = pointDis(pointPos[j], pointPos[k]);
if (isTriangle(a, b, c))
maxSize=max(maxSize,pointSize(a,b,c));
}
}
}
return maxSize;
}
double pointSizeThree(vector<Point> pointR, vector<Point> pointG, vector<Point> pointB)
{
double maxSize = INT_MIN;
for (int i = 0; i < pointR.size(); ++i)
{
for (int j = 0; j < pointG.size(); ++j)
{
for (int k = 0; k < pointB.size(); ++k)
{
double a = pointDis(pointR[i], pointG[j]);
double b = pointDis(pointR[i], pointB[k]);
double c = pointDis(pointG[j], pointB[k]);
if (isTriangle(a, b, c))
maxSize=max(maxSize,pointSize(a, b, c));
}
}
}
return maxSize;
}
int main()
{
int n = 0;
while (cin >> n)
{
char color;
vector<Point> pointR;
vector<Point> pointG;
vector<Point> pointB;
for (int i = 0; i < n; ++i)
{
cin >> color;
int x, y, z;
cin >> x >> y >> z;
Point pt = {x,y,z};
if (color == 'R')
pointR.push_back(pt);
else if (color == 'G')
pointG.push_back(pt);
else if (color == 'B')
pointB.push_back(pt);
}
double maxSize = INT_MIN;
if (pointR.size() >= 3)
maxSize = max(maxSize, pointSizeOne(pointR));
if (pointG.size() >= 3)
maxSize = max(maxSize, pointSizeOne(pointG));
if (pointB.size() >= 3)
maxSize = max(maxSize, pointSizeOne(pointB));
if (!pointR.empty() && !pointG.empty() && !pointB.empty())
maxSize = max(maxSize, pointSizeThree(pointR,pointG,pointB));
cout << setiosflags(ios::fixed) << setprecision(5) << maxSize << endl;
}
return 0;
}
四、度度熊有一个N个数的数组，他想将数组从大到小排好序，但是萌萌的度度熊只会下面这个操作：任取数组中的一个数然后将它放置在数组的最后一个位置。问最少操作多少次可以使得数组从小到大有序？
输入描述:
首先输入一个正整数N，接下来的一行输入N个整数。(N <= 50, 每个数的绝对值小于等于1000)
输出描述:
输出一个整数表示最少的操作次数。
输入例子:
4
19 7 8 25
输出例子:
2
#include<iostream>
#include<vector>
#include<algorithm>
#include<limits.h>
#include<iomanip>
#include<map>
using namespace std;
int main()
{
int n = 0;
while (cin >> n)
{
vector<int> data(n, 0);
for (int i = 0; i < n; ++i)
cin>>data[i];
map<int, int> originalPos;
for (int i = 0; i < n; ++i)
originalPos[data[i]] = i;
sort(data.begin(), data.end());
int cnt = 0;
int t = n;
for (int i = 1; i < n; ++i)
{
if (originalPos[data[i - 1]]>originalPos[data[i]])
{
originalPos[data[i]] = t++;
++cnt;
}
}
cout << cnt << endl;
}
return 0;
}
五、度度熊最近对全排列特别感兴趣,对于1到n的一个排列,度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 '>' 和 '<' )使其成为一个合法的不等式数列。但是现在度度熊手中只有k个小于符号即('<'')和n-k-1个大于符号(即'>'),度度熊想知道对于1至n任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。
输入描述:
输入包括一行,包含两个整数n和k(k < n ≤ 1000)
输出描述:
输出满足条件的排列数,答案对2017取模。
输入例子:
5 2
输出例子:
66
#include<iostream>
using namespace std;
int n, k, ans;
int dp[1005][1005];
int main() {
cin >> n >> k;
for(int i = 1; i <= n; i++)
dp[i][0] = 1;
for(int i = 2; i <= n; i++)
for(int j = 1; j <= k; j++)
dp[i][j] = (dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1)) % 2017;
cout << dp[n][k] % 2017 << endl;
return 0;
}