1、編程題小易的升級之路 小易經(jīng)常沉迷于網(wǎng)絡(luò)游戲有一次，他在玩一個(gè)打怪升級的游戲，他的角色的初始能力值為a. 在接下來的一段時(shí)間內(nèi)，他將會依次遇見n個(gè)怪物，每個(gè)怪物的防御力為b1,b2,b3.bn.如果 遇到的怪物防御力bi小于等于小易的當(dāng)前能力值c,那么他就能輕松打敗怪物，并 且使得自 己的能力值增加bi;如果bi大于c，那他也能打敗怪物，但他的能力值只能增加bi與c的最大 公約數(shù)那么問題來了，在一系列的鍛煉后，小易的最終能力值為多少 ？ 輸入描述： 對于每組數(shù)據(jù)，第一行是兩個(gè)整數(shù)n(1 *100 000)表示怪物的數(shù)量和a表示小 易的初始能力值 第二行n個(gè)整數(shù)，b1，b2.bn(1 bi n)

2、表示每個(gè)怪物的防御力 輸出描述： 對于每組數(shù)據(jù)，輸出一行.每行僅包含一個(gè)整數(shù)，表示小易的最終能力值 輸入例子： 3 50 50 105 200 5 20 30 20 15 40 100 輸出例子： 110 205 #in clude #in clude #in clude #in clude #i nclude #in clude #i nclude #i nclude using n amespace std; /* int gcd(i nt m,i nt n) return n = 0 ? m : gcd(n ,m% n); */ int gcd(i nt a,i nt b) if(!b)

3、 return a; return gcd(b,a%b); int main() int n, ack,a ns; while(sca nf(%d%d, if(an sack) ack+=gcd(ack,a ns); else ack+=a ns; prin tf(%dn,ack); return 0; 編程題炮臺攻擊 蘭博教訓(xùn)提莫之后，然后和提莫討論起約德爾人，談起約德爾人，自然少不了一個(gè)人，那 就是 黑默丁格-約德爾人歷史上最偉大的科學(xué)家.提莫說,黑默丁格最近在思考一個(gè)問題：黑默 丁格有三個(gè)炮臺，炮臺能攻擊到距離它 R的敵人(兩點(diǎn)之間的距離為兩點(diǎn)連續(xù)的距離，例如(3, 0),(0,4)之間

4、的距離是5),如果一個(gè)炮臺能攻擊到敵人，那么就會對敵人造成 1X的傷害.黑默 丁格將三個(gè)炮臺放在 N*M方格中的點(diǎn)上，并且給出敵人 的坐標(biāo)問:那么敵人受到傷害會是 多大？ 輸入描述： 第一行9個(gè)整數(shù),R,x1,y1,x2,y2,x3,y3,x0,y0.R代表炮臺攻擊的最大距 離,(x1,y1),(x2,y2), (x3,y3)代表三個(gè)炮臺的坐標(biāo).(xO,yO)代表敵人的坐標(biāo). 輸出描述： 輸出一行，這一行代表敵人承受的最大傷害,(如果每個(gè)炮臺都不能攻擊到敵人 輸出0X) 輸入例子： 1 1 1 2 2 3 3 1 2 輸出例子： 2x #in clude #i nclude #in clude

5、 using n amespace std; struct Poi nt int x,y; Poi nt(i nt x=0,i nt y=0):x(x),y(y)/構(gòu)造函數(shù)，方便代碼編寫 Poi nt(Poi nt 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; Poi nt A,B,C,P; while(sca nf(%d%d%d%d%d%d%d%d%d, R*=R; if(Dista nce(A,P)v=R) sum+; if(Dis

6、ta nce(B,P)v=R) sum+; if(Dista nce(C,P)v=R) sum+; prin tf(%dxn,sum); return 0; 1 1 1 2 2 3 3 1 2 編程題掃描透鏡 在N*M的草地上，提莫種了 K個(gè)蘑菇,蘑菇爆炸的威力極大，蘭博不想貿(mào)然去闖，而且蘑菇是隱 形的只有一種叫做掃描透鏡的物品可以掃描出隱形的蘑菇，于是他回了一趟戰(zhàn)爭學(xué)院，買了 2個(gè)掃描透鏡，一個(gè) 掃描透鏡可以掃描出（3*3）方格中所有的蘑菇，然后蘭博就可以清理掉一 些隱形的蘑菇問:蘭博最多可以清理多少個(gè)蘑菇？ 輸入描述： 第一行三個(gè)整數(shù)：N，M，K，（1 N，MK 20，K 100），N，M

7、代表了草地的大小； 接下來K行，每行兩個(gè)整數(shù)x，y（1 x N，1 y M）.代表（x，y）處提莫種了一個(gè) 蘑菇. 一個(gè)方格可以種無窮個(gè)蘑菇. 輸出描述： 輸出一行，在這一行輸出一個(gè)整數(shù)，代表蘭博最多可以清理多少個(gè)蘑菇 #i nclude #i nclude #i nclude #in clude using n amespace std; int m2525; in t vis12525; in t vis22525; int d92=-1,-1,-1,0,-1,1,0,-1,0,0,0,1,1,-1,1,0,1, 1； in li ne void sum_map(i nt x,i nt y

8、) _ for(int i=0;i0) vis1xy+; if(mx+di0y+di11) vis2xy+; in li ne int sd_sum(i nt x,i nt y,i nt i,i nt j) _ if(x=i else if(i=x-2 for(int k=0;k=x-1 else if(mxiyi0) tmp+; /con trol may reach end of non-v oid function -We rror,-Wreturn-type return tmp;/得知原因是自己定義了一個(gè)有返回值的函數(shù)，而函數(shù)結(jié) 尾卻沒有返回值； else retur n vis1i

9、j; int main() int N,M,K; while(sca nf(%d%d%d, memset(m,0,sizeof(m); memset(vis1,0,sizeof(vis1); memset(vis2,0,sizeof(vis2); for(int i=0;iK;i+) scan f(%d%d, mxy+; for(i nt i=1;i=N;i+)打表 for(i nt j=1;jv=M;j+) sum_map(i,j); _ int mmax=0; for(int i=0;i=N;i+) for(i nt j=0;j=M;j+) for(i nt ii=0;ii=N;ii+)

10、for(i nt jj=0;jj=M;jj+) mmax=max(vis1ij+sd_sum(i,j,ii,jj),mmax); _ prin tf(%dn,mmax); return 0; 題目來源：牛客網(wǎng)-網(wǎng)易2016年研發(fā)工程師編程題二 1.獎(jiǎng)學(xué)金 小v今年有n門課，每門都有考試，為了拿到獎(jiǎng)學(xué)金，小v必須讓自己的平均成 績至少為avg。每門課由平時(shí)成績和考試成績組成， 滿分為r。現(xiàn)在他知道 每門 課的平時(shí)成績?yōu)閍i ,若想讓這門課的考試成績多拿一分的話， 小v要花bi的時(shí) 間復(fù)習(xí)，不復(fù)習(xí)的話當(dāng)然就是 0 分。同時(shí)我們顯然可以發(fā)現(xiàn)復(fù)習(xí)得再多也不會拿 到超過滿分的分?jǐn)?shù)。為了拿到獎(jiǎng)學(xué)金，小 v

11、 至少要花多少時(shí)間復(fù)習(xí)。 輸入描述 : 第一行三個(gè)整數(shù) n,r,avg(n 大于等于 1 小于等于 1e5，r 大于等于 1 小于等于 1e9,avg 大于等于 1小于等于 1e6) ，接下來 n 行，每行兩個(gè)整數(shù) ai 和 bi ，均小 于等于 1e6 大于等于 1 輸出描述 : 一行輸出答案。 輸入例子 : 5 10 9 0 5 9 1 8 1 0 1 9 100 輸出例子 : 43 分析： 完成這個(gè)題目需要注意兩個(gè)問題： (1)求出最少復(fù)習(xí)時(shí)間，需要優(yōu)先選擇每分的復(fù)習(xí)時(shí)間最小的課程，那么需要 對 元素對按復(fù)習(xí)時(shí)間遞增進(jìn)行排序； (2)因?yàn)檎n程數(shù)很多，每分復(fù)習(xí)時(shí)間很大，所需最小復(fù)習(xí)時(shí)間需要

12、長整型來存 儲，以防溢出； ( 3)如果所需復(fù)習(xí)時(shí)間小于等于 0，需要特殊處理。 測試通過源碼： #include #include #include using namespace std; bool compare(const vector int regularGradeSum=0;/ 平時(shí)總分 for(int i=0;iregularGrade_efforti0regularGrade_efforti1; regularGradeSum+=regularGrade_efforti0; sort(regularGrade_effort.begin(),regularGrade_effor

13、t.end(),compare);/ / 按每分的復(fù)習(xí)時(shí)間升序排列 long long int minimumTime=0; / 因?yàn)槊糠值膹?fù)習(xí)時(shí)間很大，需要長 整型，否則溢出，不能通過測試 int needScore=courseNum*average-regularGradeSum; if (needScore =0) goto end; for(int i=0;icourseNum;+i) for(int j=0;jmaxScore-regularGrade_efforti0;+j) -needScore; minimumTime+=regularGrade_efforti1; if(n

14、eedScore=0) goto end; end: coutminimumTimeendl; 2.路燈 一條長I的筆直的街道上有n個(gè)路燈，若這條街的起點(diǎn)為0,終點(diǎn)為I，第i個(gè) 路燈坐標(biāo)為ai，每盞燈可以覆蓋到的最遠(yuǎn)距離為d,為了照明需求，所有燈的燈 光必須覆蓋整條街，但是為了省電，要求這個(gè) d最小，請找到這個(gè)最小的do 輸入描述 : 每組數(shù)據(jù)第一行兩個(gè)整數(shù) n 和 I(n 大于 0 小于等于 1000， I 小于等于 1000000000 大于0)o第二行有n個(gè)整數(shù)(均大于等于0小于等于I)，為每盞燈的坐標(biāo)，多 個(gè)路燈可以在同一點(diǎn)。 輸出描述 : 輸出答案，保留兩位小數(shù)。 輸入例子 : 7

15、15 15 5 3 7 9 14 0 輸出例子 : 2.5 分析： (1)問題的實(shí)質(zhì)是求一個(gè)數(shù)組序列中的兩個(gè)連續(xù)元素之間的最大差值，還需要 考慮首尾的特殊性； ( 2)我為了練習(xí) set 集合容器，所以使用了 set 來存儲路燈位置，當(dāng)然你也可 以使用 vector 容器。相對于 vector 容器，其好處是元素不重復(fù)，自動排序，劣 勢就是迭代器不支持算術(shù)加減操作，只支持自增 +和自減-操作。 測試通過的源碼： #include #include #include using namespace std; int main(int argc,char* argv) int n=0,l=0; set lampPos; / 默認(rèn)升序排列 while(cinnl) int pos=0; for(int i=0;ipos; lampPos.insert(pos); int maxDistance=0; for(set:iterator it=lampPos.begin();it!=-lampPos.end();+it) set:iterator nextIt=+it; -it; if(*nextIt-*it)maxDi