百度2017春招笔试真题编程题集合 练习 Apare_xzc

百度2017春招笔试真题编程题集合 解析

2020.9.3

题目链接：牛客链接

1. 买帽子

度度熊想去商场买一顶帽子，商场里有N顶帽子，有些帽子的价格可能相同。度度熊想买一顶价格第三便宜的帽子，问第三便宜的帽子价格是多少？

分析：排序，去重，输出即可。可以用unique

#include <bits/stdc++.h>
using namespace std;
int a[100];
int main(void) {int n;cin>>n;for(int i=0;i<n;++i) cin>>a[i];sort(a,a+n);int p = unique(a,a+n)-a;if(p<3) puts("-1");else printf("%d\n",a[2]); return 0;
} 

2. 度度熊回家

一个数轴上共有N个点，第一个点的坐标是度度熊现在位置，第N-1个点是度度熊的家。现在他需要依次的从0号坐标走到N-1号坐标。
但是除了0号坐标和N-1号坐标，他可以在其余的N-2个坐标中选出一个点，并直接将这个点忽略掉，问度度熊回家至少走多少距离？

分析：枚举去掉那个点，计算输出最优解即可

#include <bits/stdc++.h>
using namespace std;
int a[100]; 
int main(void) {int n;cin>>n;for(int i=0;i<n;++i) cin>>a[i];int ans = 1e9;int id = -1;for(int i=1;i<n-1;++i) {int sum = abs(a[i+1]-a[i-1]);for(int j=0;j<n-1;++j) {if(j+1==i||j==i) continue;sum += abs(a[j+1]-a[j]);} if(ans>sum) ans = sum,id = i;}cout<<ans<<endl;return 0;
} 

3. 寻找三角形

三维空间中有N个点，每个点可能是三种颜色的其中之一，三种颜色分别是红绿蓝，分别用’R’, ‘G’, 'B’表示。
现在要找出三个点，并组成一个三角形，使得这个三角形的面积最大。
但是三角形必须满足：三个点的颜色要么全部相同，要么全部不同。

分析：遍历所有不同的三元组，如果三个同色或均不同色，就用其面积更新答案。空间三角形面积用海伦公式比较容易实现，(行列式也可吧)

#include <bits/stdc++.h>
using namespace std;
struct Node{int x,y,z;Node(int _x=0,int _y=0,int _z=0):x(_x),y(_y),z(_z){}Node operator - (Node& rhs){return Node(x-rhs.x,y-rhs.y,z-rhs.z);} double getP() {return sqrt(x*x+y*y+z*z);}char color[3];void input() {scanf("%s%d%d%d",color,&x,&y,&z); }
}node[100];
bool isok(char a,char b,char c) {if(a==b&&b==c) return true;if(a!=b&&b!=c&&a!=c) return true;return false;
}
int main(void) {int n;cin>>n;for(int i=0;i<n;++i) {node[i].input();}double ans= 0;for(int i=0;i<n;++i) {for(int j=i+1;j<n;++j) {for(int k=j+1;k<n;++k) {if(isok(node[i].color[0],node[j].color[0],node[k].color[0])) {Node A = node[i]-node[j];Node B = node[i]-node[k];Node C = node[j]-node[k];double _a = A.getP();double _b = B.getP();double _c = C.getP();double P = (_a+_b+_c)*0.5;double tmp = sqrt(P*(P-_a)*(P-_b)*(P-_c));ans = max(ans,tmp);}}}}printf("%.5f\n",ans);return 0;
} 

4. 有趣的排序

度度熊有一个N个数的数组，他想将数组从小到大 排好序，但是萌萌的度度熊只会下面这个操作：
任取数组中的一个数然后将它放置在数组的最后一个位置。
问最少操作多少次可以使得数组从小到大有序？

分析：

我们自顶向下地考虑，答案一定不超过n，因为我们可以先把最小的放到后面，然后第二小，第三小… 最后把最大的放到后面。最后一步一定是把最大的放到最后面。 那么前面的步骤是否可以省略一些呢？我们看样例，最小的7 8已经相对有序排列了。那么就可以不管他们。所以，如果从最小的开始，往后的第2小，第三小的下标都一次递增(不用挨着)，那么我们就可以不用管这些相对升序的序列。 答案就是n-从最小的开始升序序列的长度。 因为后面的大数归位后，他们就自动有序了。

#include <bits/stdc++.h>
using namespace std;
int a[100],b[100];
int main(void) {int n;cin>>n;for(int i=0;i<n;++i) cin>>a[i],b[i] = a[i];sort(b,b+n);int i = 0,j = 0;int cnt = 0;while(i<n&&j<n) {if(a[i]==b[j]) ++i,++j,++cnt;else ++i;}cout<<n-cnt<<endl;return 0;
} 

5. 不等式数列

度度熊最近对全排列特别感兴趣,对于1到n的一个排列,度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 ‘>’ 和 ‘<’ )使其成为一个合法的不等式数列。但是现在度度熊手中只有k个小于符号即(’<’’)和n-k-1个大于符号(即’>’),度度熊想知道对于1至n任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。

分析：

看数据范围一定是DP。
设dp[i][j]为把前i个数(1,2,3,…i)插入到序列中, 有j个小于号(当然就有i-1-j个大于号)的方案数。
那么，现在如果已经插了i-1个数，要插入i这个数，

1. 如果插在最前面，多了1个大于号(i比前面已经插入的都大) dp[i][j] += dp[i-1][j]
2. 如果插在最后面，多了1个小于号 dp[i][j] += dp[i-1][j-1
3. 如果插在某一个小于号之间(j-1个位置)，那么多一个大于号 dp[i][j] += dp[i][j]*(j-1)
4. 如果插在某一个大于号之间(i-1-j个位置)，那么多一个小于号 dp[i][j] += dp[i][j-1]*(i-1-j)

故：dp[i][j] = (dp[i-1][j-1]*(i-j)+dp[i-1][j]*(j+1))%2017;

#include <bits/stdc++.h>
using namespace std;
const int mod = 2017;
const int N = 1002;
int dp[N][N]; //dp[i][j]表示将前i个数插入到序列中，有j个小于号(i-1-j个大于号)的情况 
int main(void) {int n,k;cin>>n>>k;//1<3>2//现在插入4，如果4插在最前面，则相当于多了一个大于号//如果插在最后面，多了个小于号//如果插在一个小于号之间，多了个大于号//如果插在大于号之间，多了个小于号 for(int i=1;i<=n;++i) dp[i][0] = 1; //前i个数插入，0个小于号，说明只能是降序排列 for(int i=2;i<=n;++i) {for(int j=1;j<=k&&j<i;++j) {dp[i][j] = (dp[i-1][j-1]*(i-j)+dp[i-1][j]*(j+1))%2017;}}cout<<dp[n][k]<<endl;return 0;
}