网易笔试编程题2016

1、编程题 小易的升级之路小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2,b3.bn. 如果遇到的怪物防御力bi小于等于小易的当前能力值c,那么他就能轻松打败怪物,并 且使得自己的能力值增加bi;如果bi大于c,那他也能打败怪物,但他的能力值只能增加bi 与c的最大公约数.那么问题来了,在一系列的锻炼后,小易的最终能力值为多少?输入描述:对于每组数据,第一行是两个整数n(1n<100000)表示怪物的数量和a表示小易的初始能力值.第二行n个整数,b1,b2.bn(1bin)表示每

2、个怪物的防御力输出描述:对于每组数据,输出一行.每行仅包含一个整数,表示小易的最终能力值输入例子:3 5050 105 2005 2030 20 15 40 100输出例子:110205#include<iostream>#include<cstdio>#include<string>#include<vector>#include<list>#include<deque>#include<stdio.h>#include<algorithm>using namespace std;/*int gc

3、d(int m,int n) return n = 0 ? m : gcd(n,m%n);*/int gcd(int a,int b) if(!b) return a; return gcd(b,a%b);int main() int n,ack,ans; while(scanf("%d%d",&n,&ack)!=EOF) while(n-) scanf("%d",&ans); if(ans>ack) ack+=gcd(ack,ans); else ack+=ans; printf("%dn",ack);

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

5、y1),(x2,y2),(x3,y3)代表三个炮台的坐标.(x0,y0)代表敌人的坐标.输出描述:输出一行,这一行代表敌人承受的最大伤害,(如果每个炮台都不能攻击到敌人,输出0×)输入例子:1 1 1 2 2 3 3 1 2输出例子:2x#include<iostream>#include<stdio.h>#include<math.h>using namespace std;struct Point int x,y; Point(int x=0,int y=0):x(x),y(y)/构造函数，方便代码编写 Point(Point &a):

6、x(a.x),y(a.y);inline int Distance(Point A,Point B) return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);int main() int R; Point A,B,C,P; while(scanf("%d%d%d%d%d%d%d%d%d",&R,&A.x,&A.y,&B.x,&B.y,&C.x,&C.y,&P.x,&P.y)!=EOF) int sum=0; R*=R; if(Distance(A,P)<=R)

7、 sum+; if(Distance(B,P)<=R) sum+; if(Distance(C,P)<=R) sum+; printf("%dxn",sum); return 0;/1 1 1 2 2 3 3 1 2编程题 扫描透镜在N*M的草地上,提莫种了K个蘑菇,蘑菇爆炸的威力极大,兰博不想贸然去闯,而且蘑菇是隐形的.只 有一种叫做扫描透镜的物品可以扫描出隐形的蘑菇,于是他回了一趟战争学院,买了2个扫描透镜,一个 扫描透镜可以扫描出(3*3)方格中所有的蘑菇,然后兰博就可以清理掉一些隐形的蘑菇. 问:兰博最多可以清理多少个蘑菇?输入描述:第一行三个整数:N,

8、M,K,(1N,M20,K100),N,M代表了草地的大小;接下来K行,每行两个整数x,y(1xN,1yM).代表(x,y)处提莫种了一个蘑菇.一个方格可以种无穷个蘑菇.输出描述:输出一行,在这一行输出一个整数,代表兰博最多可以清理多少个蘑菇.#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>using namespace std;int m2525;int vis12525;int vis22525;int d92=-1,-1,-1,0,-1,1,0,

9、-1,0,0,0,1,1,-1,1,0,1,1;inline void sum_map(int x,int y) for(int i=0;i<9;i+) if(mx+di0y+di1>0) vis1xy+; if(mx+di0y+di1>1) vis2xy+; inline int sd_sum(int x,int y,int i,int j) if(x=i&&y=j) return vis2ij; else if(i>=x-2&&i<=x+2&&j>=y-2&&j<=y+2) int t

10、mp=0; for(int k=0;k<9;k+) int xi=i+dk0; int yi=j+dk1; if(xi>=x-1&&xi<=x+1&&yi>=y-1&&yi<=y+1) if(mxiyi>1) tmp+; else if(mxiyi>0) tmp+; /control may reach end of non-void function -Werror,-Wreturn-type return tmp;/得知原因是自己定义了一个有返回值的函数，而函数结尾却没有返回值； else retur

11、n vis1ij;int main() int N,M,K; while(scanf("%d%d%d",&N,&M,&K)!=EOF) int x,y; memset(m,0,sizeof(m); memset(vis1,0,sizeof(vis1); memset(vis2,0,sizeof(vis2); for(int i=0;i<K;i+) scanf("%d%d",&x,&y); mxy+; for(int i=1;i<=N;i+)/打表 for(int j=1;j<=M;j+) sum_

12、map(i,j); int mmax=0; for(int i=0;i<=N;i+) for(int j=0;j<=M;j+) for(int ii=0;ii<=N;ii+) for(int jj=0;jj<=M;jj+) mmax=max(vis1ij+sd_sum(i,j,ii,jj),mmax); printf("%dn",mmax); return 0;题目来源：牛客网-网易2016年研发工程师编程题二。1. 奖学金小v今年有n门课，每门都有考试，为了拿到奖学金，小v必须让自己的平均成绩至少为avg。每门课由平时成绩和考试成绩组成，满分为r。

13、现在他知道 每门课的平时成绩为ai ,若想让这门课的考试成绩多拿一分的话，小v要花bi 的时间复习，不复习的话当然就是0分。同时我们显然可以发现复习得再多也不会拿到超过满分的分数。为了拿到奖学金，小v至少要花多少时间复习。输入描述: 第一行三个整数n,r,avg(n大于等于1小于等于1e5，r大于等于1小于等于1e9,avg大于等于1小于等于1e6)，接下来n行，每行两个整数ai和bi，均小于等于1e6大于等于1输出描述: 一行输出答案。输入例子: 5 10 9 0 5 9 1 8 1 0 1 9 100输出例子: 43分析： 完成这个题目需要注意两个问题： （1）求出最少复习时间，需要优先选

14、择每分的复习时间最小的课程，那么需要对<平时成绩，复习时间>元素对按复习时间递增进行排序； （2）因为课程数很多，每分复习时间很大，所需最小复习时间需要长整型来存储，以防溢出； （3）如果所需复习时间小于等于0，需要特殊处理。测试通过源码：#include <iostream>#include <vector>#include <algorithm>using namespace std;bool compare(const vector<int>& vec0,const vector<int>& vec1

15、) return vec01<vec11; /升序排列int main(int argc,char* argv) int courseNum=0,maxScore=0,average=0; while(cin>>courseNum>>maxScore>>average) vector<vector<int> > regularGrade_effort(courseNum,vector<int>(2,0); int regularGradeSum=0;/平时总分 for(int i=0;i<courseNum;+

16、i) cin>>regularGrade_efforti0>>regularGrade_efforti1; regularGradeSum+=regularGrade_efforti0; sort(regularGrade_effort.begin(),regularGrade_effort.end(),compare);/按每分的复习时间升序排列 long long int minimumTime=0; /因为每分的复习时间很大，需要长整型，否则溢出，不能通过测试 int needScore=courseNum*average-regularGradeSum; if

17、(needScore <=0) goto end; for(int i=0;i<courseNum;+i) for(int j=0;j<maxScore-regularGrade_efforti0;+j) -needScore; minimumTime+=regularGrade_efforti1; if(needScore=0) goto end; end: cout<<minimumTime<<endl; 2.路灯一条长l的笔直的街道上有n个路灯，若这条街的起点为0，终点为l，第i个路灯坐标为ai，每盏灯可以覆盖到的最远距离为d，为了照明需求，所有

18、灯的灯光必须覆盖整条街，但是为了省电，要求这个d最小，请找到这个最小的d。输入描述: 每组数据第一行两个整数n和l（n大于0小于等于1000，l小于等于1000000000大于0）。第二行有n个整数(均大于等于0小于等于l)，为每盏灯的坐标，多个路灯可以在同一点。输出描述: 输出答案，保留两位小数。输入例子: 7 15 15 5 3 7 9 14 0输出例子: 2.5分析： （1）问题的实质是求一个数组序列中的两个连续元素之间的最大差值，还需要考虑首尾的特殊性； （2）我为了练习set集合容器，所以使用了set来存储路灯位置，当然你也可以使用vector容器。相对于vector容器，其好处是元素不重复，自动排序，劣势就是迭代器不支持算术加减操作，只支持自增+和自减操作。测试通过的源码：#include <iostream>#include <set>#include <iomanip>using namespace std;in