网易游戏技术岗在线编程题(一)

题目来源:牛客网-网易2016年研发工程师编程题

1.小易的升级之路

小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2,b3…bn. 如果遇到的怪物防御力bi小于等于小易的当前能力值c,那么他就能轻松打败怪物,并 且使得自己的能力值增加bi;如果bi大于c,那他也能打败怪物,但他的能力值只能增加bi 与c的最大公约数.那么问题来了,在一系列的锻炼后,小易的最终能力值为多少?

输入描述: 对于每组数据,第一行是两个整数n(1≤n<100000)表示怪物的数量和a表示小易的初始能力值. 第二行n个整数,b1,b2…bn(1≤bi≤n)表示每个怪物的防御力

输出描述: 对于每组数据,输出一行.每行仅包含一个整数,表示小易的最终能力值

输入例子: 3 50 50 105 200 5 20 30 20 15 40 100

输出例子: 110 205

测试通过的源码:

#include <stdio.h>

#include  <iostream>
using namespace std;

//辗转相除法求两数最大公约数(欧几里德算法)
int euclid(int a,int b){
    //要求a和b是正整数
    if(a<=0||b<=0) 
        return -1;
    int tmp=a%b;
    while(tmp!=0){
        a=b;
        b=tmp;
        tmp=a%b;
    }
    return b;
}

int monsterNum_easePower[2]={2};
int monsterPower[100000]={0};

int main(int argc,char* argv[]){
    //while(cin.peek()!=EOF){ //不行
    //while(cin.peek()!=EOF&&cin.peek()!='\n'&&cin.peek()!=' '){不行
    while(cin>>monsterNum_easePower[0]>>monsterNum_easePower[1]){
        //cin>>monsterNum_easePower[0]>>monsterNum_easePower[1];
        for(int i=0;i<monsterNum_easePower[0];++i){
            cin>>monsterPower[i];
            if(monsterPower[i]>monsterNum_easePower[1])
                monsterNum_easePower[1]+=euclid(monsterNum_easePower[1],monsterPower[i]);
            else
                monsterNum_easePower[1]+=monsterPower[i];
        }
        cout<<monsterNum_easePower[1]<<endl;
    }
}

注意事项: (1)在线编程要想通过测试案例必须要个按照其输入和输出数据的格式进行操作,要严格遵守这种游戏的规则; (2)为什么while(cin>>a)这种形式可以作为循环结束的判定条件,cin>>a;实际上是调用cin.operator>>(a);,其返回值istream&,也就是while(cin)需要对输入流对象cin做真假判断。实际上这里会进行隐式转换,因为cin有两个运算符重载的成员函数,分别为operator void *() constbool operator!() constoperator void *() const函数在while(cin)或是if(cin)时被调用,将流对象转换成void*类型。bool operator!() const函数在while(!cin)或是if(!cin)时被调用,将流对象转换成bool类型。其实现为:

operator void*() const  
{ return this->fail() ? 0 : const_cast<basic_ios*>(this); }  

bool operator!() const  
{ return this->fail(); }  

所以,可以简单的理解调用过程等价为如下形式:

while(cin)  =====> while(!cin.fail())              //while the stream is OK
while(!cin) =====> while(cin.fail())               //while the stream is NOT OK

具体参见博文:while(cin)和while(!cin)的原理分析

(3)判断测试数据是否读取完,不能使用下面两行,真不知道其输入的测试数据是以什么样的形式结束的,有知道的往右也可留言告知。

    //while(cin.peek()!=EOF)
    //while(cin.peek()!=EOF&&cin.peek()!='\n'&&cin.peek()!=' ')

2.炮台攻击

兰博教训提莫之后,然后和提莫讨论起约德尔人,谈起约德尔人,自然少不了一个人,那 就是黑默丁格——约德尔人历史上最伟大的科学家. 提莫说,黑默丁格最近在思考一个问题:黑默丁格有三个炮台,炮台能攻击到距离它R的敌人 (两点之间的距离为两点连续的距离,例如(3,0),(0,4)之间的距离是5),如果一个炮台能攻击 到敌人,那么就会对敌人造成1×的伤害.黑默丁格将三个炮台放在N*M方格中的点上,并且给出敌人 的坐标. 问:那么敌人受到伤害会是多大?

输入描述: 第一行9个整数,R,x1,y1,x2,y2,x3,y3,x0,y0。R代表炮台攻击的最大距离,(x1,y1),(x2,y2), (x3,y3)代表三个炮台的坐标.(x0,y0)代表敌人的坐标。

输出描述: 输出一行,这一行代表敌人承受的最大伤害,(如果每个炮台都不能攻击到敌人,输出0×)

输入例子: 1 1 1 2 2 3 3 1 2

输出例子: 2x

通过测试的源码:

#include  <iostream>
using namespace std;

int R,x1,y1,x2,y2,x3,y3,x0,y0;

//func:判断两点间的具体是否在范围R内
//para:R:炮台攻击范围;敌人坐标:(x0,y0);炮台坐标:(x1,y1)
bool withinRange(int R,int x0,int y0,int x1,int y1){
    if((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1)>R*R)
        return false;
    else
        return true;
}

int main(int argc,char* argv[]){
    int barbetteNum=0;
    while(cin>>R>>x1>>y1>>x2>>y2>>x3>>y3>>x0>>y0){
        barbetteNum=0;
        if(withinRange(R,x0,y0,x1,y1))
            ++barbetteNum;
        if(withinRange(R,x0,y0,x2,y2))
            ++barbetteNum;
        if(withinRange(R,x0,y0,x3,y3))
            ++barbetteNum;
        cout<<barbetteNum<<'x'<<endl;
    }
}

3.扫描透镜

在N*M的草地上,提莫种了K个蘑菇,蘑菇爆炸的威力极大,兰博不想贸然去闯,而且蘑菇是隐形的.只 有一种叫做扫描透镜的物品可以扫描出隐形的蘑菇,于是他回了一趟战争学院,买了2个扫描透镜,一个 扫描透镜可以扫描出(3*3)方格中所有的蘑菇,然后兰博就可以清理掉一些隐形的蘑菇. 问:兰博最多可以清理多少个蘑菇?

输入描述: 第一行三个整数:N,M,K,(1≤N,M≤20,K≤100),N,M代表了草地的大小; 接下来K行,每行两个整数x,y(1≤x≤N,1≤y≤M).代表(x,y)处提莫种了一个蘑菇. 一个方格可以种无穷个蘑菇.

输出描述: 输出一行,在这一行输出一个整数,代表兰博最多可以清理多少个蘑菇.

分析: 对于我这种游戏经验匮乏的人,开始一直没有理清楚题意,实际该题目需要注意两个问题: 首先,当矩阵N行M列,注意N<3 或者M<3的情况;

其次,每个扫描镜只能用一次,每个扫描镜在每个格子内一次只能清理一个蘑菇。要想扫描镜能够清除最多的蘑菇,则扫描镜的区域拥有蘑菇的方格数要最大。

通过测试的代码:

#include <string.h>

#include <vector>
#include  <iostream>
using namespace std;


int mushroomNum=0;                  //蘑菇总数
int N,M;                            //草地长宽(格数):N行M列

//func:给定3*3方格最下角方格坐标和草地的长宽和蘑菇分布计算蘑菇数目求3*3方格内的蘑菇数目
//para:(x,y):第x行y列的方格;N:草地行数,M:草地列数;grassLandMushroom:草地蘑菇数量
int getMushroomGridNum(int x,int y,int N,int M,int grassLandMushroom[][20]){
    int mushroomGridNum=0;
    for(int i=0;i<3;++i)
        for(int j=0;j<3;++j){
            if(x+i<N&&y+j<M&&grassLandMushroom[x+i][y+j]>0)
                ++mushroomGridNum;
        }
    return mushroomGridNum;
}

//func:获取草地中3*3方格中拥有蘑菇的最多方格数
//para:N:草地行数,M:草地列数;grassLandMushroom:草地蘑菇数量
vector<int> getMaxMushroomNumPos(int N,int M,int grassLandMushroom[][20]){
    //构造三个0,pos[0]:行,pos[1]:列,pos[2]:有蘑菇的方格数
    vector<int> pos(3,0); 
    int maxMushroomGridNum=0;
    //maxMushroomNum=getMushroomNum(0,0,N,M,grassLandMushroom);

    int tmp=0;
    for(int i=0;i<N;++i){
        for(int j=0;j<M;++j){
            tmp=getMushroomGridNum(i,j,N,M,grassLandMushroom);
            if(tmp>maxMushroomGridNum){
                maxMushroomGridNum=tmp;
                pos[0]=i;
                pos[1]=j;
                pos[2]=maxMushroomGridNum;
            }
            if(j>=M-3) break;
        }
        if(i>=N-3) break;
    }
    return  pos;
}

//func:更新3*3方格内草地蘑菇数量
//para:(x0,y0):第x0行y0列的方格;N:草地行数,M:草地列数;grassLandMushroom:草地蘑菇数量
void updateMushroomNum(int x,int y,int N,int M,int grassLandMushroom[][20]){
    for(int i=0;i<3;++i)
        for(int j=0;j<3;++j){
            if(x+i<N&&y+j<M&&grassLandMushroom[x+i][y+j]>0)
                --grassLandMushroom[x+i][y+j];
        }
}

int main(int argc,char* argv[]){
    int x=0,y=0;
    while(cin>>N>>M>>mushroomNum){

        int grassLandMushroom[20][20]={0};  //草地蘑菇分布

        for(int i=0;i<mushroomNum;++i){
            cin>>x>>y;
            ++grassLandMushroom[x-1][y-1];
        }
        //扫描镜第一次扫描
        vector<int> pos1=getMaxMushroomNumPos(N,M,grassLandMushroom);
        updateMushroomNum(pos1[0],pos1[1],N,M,grassLandMushroom);

        //扫描镜第二次扫描
        vector<int> pos2=getMaxMushroomNumPos(N,M,grassLandMushroom);

        cout<<pos1[2]+pos2[2]<<endl;
    }
}

注意: 使用暴力的方法,逻辑上还是很简单的。但是,这一道题花了我5个多小时,因为第二个测试案例总是通不过。但是在本地机器却可以正确解出第二个测试案例的结果,百思不得其解。对比了网上通过的版本,仔细研究,才意外的发现发现我将二维数组grassLandMushroom[20][20]放到while循环体内定义为局部变量就行了,真是坑爹啊。尽管我每次循环结束都会将其置空,但是在牛客网在线编程还是通不过,不知为何,谨此吐槽,纪念!

参考文献

[1]while(cin)的结束判断. [2]牛客网:http://www.nowcoder.com/test/question/analytic?tid=2679679. [3]另一位网友的实现.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

kaggle-2美国人口普查年收入50K分类

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

38830
来自专栏数值分析与有限元编程

Newton–Raphson法解串联弹簧问题

如图所示的串联弹簧,F=100,弹簧刚度为k1 = 50 + 500u ,k2 = 100+ 200u ,u是弹簧伸长量,则平衡方程为 ? ? k1,k2带入得...

29160
来自专栏Python攻城狮

Python数据科学(九)- 使用Pandas绘制统计图表1.信息可视化

因为人对图像信息的解析效率比文字更高,所以可视化可以使数据更为直观,便于理解,使决策变得高效,所以信息可视化就显得尤为重要。

11430
来自专栏黑豆梨的曲线机器学习路线

数值方式求解圆周率π

如图,假设圆的半径为1,可知圆的周长为2π,我们现在只需要用积分的方法求出 1/4 周长,即为π/2。

50280
来自专栏机器学习算法与Python学习

Encoder-Decoder自动生成对联,要试试么?

另外,点击阅读原文尝试微软的自动对联系统(http://duilian.msra.cn/app/couplet.aspx)

13400
来自专栏数据派THU

手把手教你由TensorFlow上手PyTorch(附代码)

来源:机器之心 作者:Illarion Khlestov 本文为你解读PyTorch 的易用性。 当我第一次尝试学习 PyTorch 时,没几天就放弃了。和 ...

98140
来自专栏数据科学与人工智能

【陆勤践行】最流行的4个机器学习数据集

机器学习算法需要作用于数据,而数据的本质则决定了应用的机器学习算法是否合适,而数据的质量也会决定算法表现的好坏程度。所以会研究数据,会分析数据很重要。本文作为学...

222100
来自专栏趣学算法

算法之美——算法复杂性

《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825

29410
来自专栏WOLFRAM

Mathematica 11在代数与数论中的新功能

19550
来自专栏月色的自留地

从锅炉工到AI专家(3)

22290

扫码关注云+社区

领取腾讯云代金券