网易雷火2020秋招平台开发笔试-编程题
题一
题目描述
AABB盒（Axis-Aligned Bounding Box）是描述3D世界包围盒的一个长方体，他的每一边都平行于一个坐标平面，中心点，长、宽、高可以彼此不同，如下图所示：
现在给定N个长方体的物体，(给出中心坐标()）和对应轴的边长(xlen_i,ylen_i, zlen_i)）,和M个球（中心坐标(x y.z)半径rj)，问这些物体有多少个完全被包围在一个大的AABB盒子里(中心坐标x,y,z)，长宽高(xlen,ylen,zlen))
输入描述
每个测试输入包含1个测试用例
第一行，6个整数，x、y、z、xlen、ylen、zlen,分别表示大的AABF盒的中心坐标和3条轴长。
第二行，用格隔开的两个整数和M，含义见题目描述，其中1<N<100,0<M<100。
接下来行，每行6个整数，xi、yi、zi、xlen_i、ylen_i、zlen_i,表示一个长方体的中心坐标和三条轴长。
接下来M行，每行4个整数，xj、yj、zj、rj，表示一个球的中心坐标和半径。
输出描述
输出一个整数，以回车结束:有多少个物体完全被大的AABB盒包围(包围是指物体全部处于包围盒内部，与包围盒完全不重叠也不相切)。
示例1
输入
0 0 0 10 10 10
3 2
1 1 1 2 2 2
4 5 6 5 5 5
8 2 2 2 2 2
0 0 0 3
8 8 8 4
输出
2
示例2
输入
0 0 0 10 10 10
5 4
-1 1 1 1 1 1
-7 8 -9 3 3 3
3 3 3 7 8 9
-9 9 0 1 1 1
-4 -3 -2 5 5 5
-5 -5 -5 4
-5 5 6 4
-4 5 -3 4
6 4 3 5
输出
1
思路：这种三维问题，一个惯用的思路就是降维思考以及分维度观察，维度增加后，依旧会有相似的结论。
如上图所示，设圆心为(x1,y1)，长方形中心为(x,y)，对于圆形包围在长方形内部，我们单独看x轴方向与y轴方向，会有结论：
值得注意的是，在本题中，我们为了避免浮点的精度误差，因此使用了整数，为了避免整数/2由于整除造成的数据丢失，因此我们将不等式两边同时乘2得到如下关系式：
推广到三维中，我们还需要增加对z轴方向的约束，类似于x和y会有：
再来看长方形的情况，从圆形中借鉴思想，我们可以同样推出：
同样，为了避免整除带来的误差，我们两边同乘2：
增加z维度的约束后，需要增加不等式：
因此，遇A不决先看B，没准借鉴解决A2333。
代码：
#include<bits/stdc++.h>
using namespace std;
const int MaxN = 110;
int x, y, z, xlen, ylen, zlen;
// x轴距离+半径 <= x轴空间范围 防止整除 两边乘2
bool ContainSphere(int x1,int y1,int z1,int r){
return 2 * ( abs(x1 - x) + r ) < xlen && 2 * ( abs(y1 - y) + r ) < ylen && 2 * ( abs(z1 - z) + r ) < zlen ;
}
// x轴距离 + 小方块x的一半 <= 大方块x的一半
bool ContainRect(int x1,int y1,int z1,int LenX,int LenY,int LenZ){
return 2 * abs(x1 - x) + LenX < xlen && 2 * abs(y1 - y) + LenY < ylen && 2 * abs(z1 - z) + LenZ < zlen ;
}
int main(){
int N, M, i, ans = 0 , x1 ,y1, z1, r, LenX, LenY, LenZ;
cin >> x >> y >> z >> xlen >> ylen >> zlen >> N >> M;
for( i = 1 ; i <= N ; ++ i ){
cin >> x1 >> y1 >> z1 >> LenX >> LenY >> LenZ;
if(ContainRect(x1, y1, z1, LenX, LenY, LenZ ) ) ++ ans;
}
for( i = 1 ; i <= M ; ++ i ){
cin >> x1 >> y1 >> z1 >> r;
if( ContainSphere(x1 , y1 , z1 , r) ) ++ ans;
}
cout << ans;
}题目二
题目描述
游戏有N个版本，分别是V1,V2, v3...Vn。
任意两个版本i和j之间(i<j)，都有一个补丁Pij，这个补丁可以把i版本升级到j版本，这个补丁的大小是Sij，安装这个补丁需要Tij秒。
玩家也可以选择直接下截任意一个版本的完整内容，每个版本的完整内容大小SVi。已知玩家当前的下载速度是t，也就意味着下载一个S大小的补丁或者完整安装包，需要耗时S/t秒。
我们看一个具体的例子，假设玩家当前游戏版本为Vi，他要将游戏升级到V，可能有以下的升级方式：
先升级到一个中间版本k(i<k<j)，再升级到版本j，则升级耗时为Sik/t + Tik+ Skj/t +Tkj;
先下载一个低版本k(k<i)，再升级到版本j，则升级耗时为SVk/t +Skj/t +Tkj;
或者选择从1到j中间一系列版本的其他可能的升级操作，这里就不具体描述了。
给定以上数据，并给定玩家当前的版本X，请计算玩家要升级到最新版本（版本N)，最优的策略需要耗时多少秒。
补丁下载和安装不能并行，只能串行;不允许反向补丁，不能把高版本patch成低版本。
输入描述
第一行是2个正整数，表示有x个版本（1<=N<= 100），当前是x版本（1<=x<N）。
第二行是1个数字，表示下载速度t。
第三行N个数字，表示每个版本完整大小。
下面共N-1行N-i列个数字（第i行有N-i个数字），表示从i版本（第i行）升级到i+k版本（第k列）的补丁大小。
下面共N-1行N-i列个数字（第i行有N-i个数字），表示从i版本（第i行）升级到i+k版本（第k列）的补丁安装时间。
输出描述
输出1个数字，表示最优策略耗时多少秒，精确到小数点后2位。
示例一
输入
3 1
1
1 2 3
1 2
1
1 2
1
输出
3.00
首先，由题目可知，我们直接从版本i升级到版本j(i<j)，注意是直接升级，没有中间过程，那么花费的最少时间应该是min(下载i->j的补丁并安装补丁，直接下载并安装j版本的完整包[本题中，下载并安装完整包的时间耗费为SVi/t])：
但是题目中还给出了先下载低版本，再升级的方案，因此，对于i>j的情况，我们会有：
于是实际上我们得到了一个有向图，需要在这个有向图上找到任意一个节点i(i!=N)到N的最短路。为什么不是X到N呢，因为题目中说了可以直接下载一个低版本，再从低版本更新过去。这是一个多源最短路问题，并且n<=100，因此可以选择使用Flody算法。另外，需要注意的是，由于本题给出了初始版本X，因此从任意版本到达X的代价必为0。
#include<bits/stdc++.h>
using namespace std;
double Patch_Size[110][110],Patch_Time[110][110],dp[110][110],Full_Size[110];
int main(){
int N, X, i, j, k;
double t, ans = 10000000;
cin >> N >> X >> t;
for( i = 1 ; i <= N ; ++ i ){
cin >> Full_Size[i];
Full_Size[i] /= t;
}
for( i = 1 ; i <= N ; ++ i ){
for( j = i + 1 ; j <= N ; ++ j ){
cin >> Patch_Size[i][j];
Patch_Size[i][j] /= t ;
}
}
for( i = 1 ; i <= N ; ++ i ){
for( j = i + 1 ; j <= N ; ++ j ){
cin >> Patch_Time[i][j];
Patch_Time[i][j] += Patch_Size[i][j] ;
}
}
for(k = 1; k <= N ; ++ k){
for(i = 1; i <= N ; ++ i){ // i->k + k->j
for( j =1 ; j <= N; ++ j){
dp[i][j] = j == X ? 0 : Full_Size[j]; // 在j!=X时 想要到达j 都可以选择 直接下载一个j 并安装
if( i <= k && k <= j ){
dp[i][j] = min(dp[i][j], dp[i][k] + Patch_Time[k][j]);
}
}
}
}
for( i = 1 ; i <= N ; ++ i){
ans = min(ans, dp[i][N]);
}
printf("%.2f",ans);
}
当然了，其实我们的终点是固定的，因此，如果我们反向考虑，把有向边从i->j的权值，建立成从j->i的权值，这样只需要从终点N开始，跑单源最短路就可以了！！！需要注意的是，由于存在初始版本X，因此，当我们跑完最短路之后，不可忘记，在计算答案的时候，所有非X的点，他们变成N的代价为
因为可能(可以升级补丁或者下载版本)也可能
(只能下载版本)，因此我们直接累加上最小变化代价。
#include<bits/stdc++.h>
using namespace std;
double Patch_Size[110][110],Patch_Time[110][110],dp[110][110],Full_Size[110],Cost_Time[110][110],dist[110];
bool inque[110];
void SPFA(int S,int N){
int i;
queue<int> que;
que.push(S);
for( i = 1; i <= N ; ++ i){
dist[i] = DBL_MAX / 4;
}
dist[S] = 0;
inque[S] = true;
while(que.size()){
S = que.front();
que.pop();
inque[S] = false;
for( i = 1 ; i <= N ; ++ i ){
if( i == S ) continue; // 只有 S-S 是没有意义的
if( dist[i] > dist[S] + Cost_Time[S][i] ){
dist[i] = dist[S] + Cost_Time[S][i];
que.push(i);
inque[i] = true;
}
}
}
}
// Cost_Time[i][j] : 从j到i需要的时间
int main(){
int N, X, i, j, k;
double t, ans = DBL_MAX;
cin >> N >> X >> t;
for( i = 1 ; i <= N ; ++ i ){
cin >> Full_Size[i];
Full_Size[i] /= t;
}
for( i = 1 ; i <= N ; ++ i ){
for( j = 1 ; j <= N ; ++ j ){ //反向建边 所有的版本 只要想到i，都可以走下载完整版的路
Cost_Time[j][i] = Full_Size[j];
}
}
for( i = 1 ; i <= N ; ++ i ){
for( j = i + 1 ; j <= N ; ++ j ){
cin >> Patch_Size[j][i]; //从i->j的权值 建成从 j->i的
Patch_Size[j][i] /= t ;
}
}
for( i = 1 ; i <= N ; ++ i ){
for( j = i + 1 ; j <= N ; ++ j ){
cin >> Patch_Time[j][i];
Patch_Time[j][i] += Patch_Size[j][i] ;
Cost_Time[j][i] = min(Cost_Time[j][i],Patch_Time[j][i]);
}
}
SPFA(N,N);
for( i = 1 ; i < N ; ++ i){
dist[i] += i == X ? 0 : Cost_Time[X][i];
ans = min(ans, dist[i]);
}
printf("%.2f",ans);
}
上一篇： hashMap底层实现