集训队作业-会飞小猪解题报告

【正文

一、问题描述某一列的小猪朝向同一个方向。tiin出ti二 问题分析优解。可以设计出一些贪心策略解决这题。算法一 优化一：不一定要等第i只猪到达了猪圈后才去处理第i+1只猪。只需它就能够到达猪圈。当然吹后面的猪的时候，不能影响前面的猪的方向。这样就节省了很多无谓的等待时间。优化二：把随便找一只猪改成挑一只离猪圈距离Si中最小的猪。这样算法二引入一个量：状态的值。对于每个状态 值来评价状态的好坏。在这题中计算状态的值的方法为：状态的值nSi。其中Si表示第i只猪离它最近的猪圈的距离 优化：M值越小，并不一定说明状态越好。因为有可能两只猪i,j。Si,Sj取到kM值并不能准确反引入随机化，每次不一定取最小的M值，因为有时候取到第k小的M值反算法三k:←Random(Rate)ifk>0thenMin←M

不同的数据，取到最优解的时候，MaxnRate1∞23552∞373∞64226∞77∞385922∞5【附录1、ProgramConstMaxn=1000;h:array[1..4,1..2]ofTypea:array[1..Maxn2,1..Maxn2]ofShortint;Value:array[1..Maxn2,1..Maxn2]ofLongint;d:array[1..2,1..Maxn2]ofLongint;g:array[1..9,1..2]ofLongint;Blow:array[1..8,1..Maxn2]ofLongint;Point,Step:array[1..Maxn1]ofLion;Pig,Pig_bak:array[1..Maxn1]ofLion1;RestTime:array[1..Maxn1]ofLongint;ProcedureVari,k,Min:longint;fori:=1tomdoforj:=1to9doifk<MinthenVari,j:Longint;fori:=1tomdoif(Point[i].x=x)and(Point[i].y=y)thenforj:=itom-1doProcedureMove(Varx,y,bj:Longint);Casebjofifx>nthenelseifx<1thenx:=n;ify>ntheny:=1elseify<1theny:=n;ProcedureMovePigs(VarNow1,Now2:longint;bj1,bj2:longint);Vari,j,Now1_bak,Now2_bak:longint;fori:=1tototdoifa[Pig[i].x,Pig[i].y]=1thenifi<=Now1_bakthendec(Now1);ifi<=Now2_bakthendec(Now2);forj:=tot1+1totot-1doend;End;fori:=1tototProcedureVarifValue[x,y]<0thenValue[x,y]:=Cal(x,y);WhileTime<Maxnfori:=1tototdofori:=1ton fori:=1tondoforj:=1to4doifk<MinthenifRan>0thenfori:=1tototif(((bj1=4)or(bj1=6))and(bj2=Pig[i].x))thenPig[i].Dir:=bj1;iftot=0thenbreak;fori:=1tomdoProcedureVari,j,Start,k,Now,x,y,yy, Whilei<totdoWhilebbdoforj:=StarttototdoifDis<MinthenifMin=Maxlongintthenbak:=Pig[Start];Pig[Start]:=Pig[k];Pig[k]:=bak;bak:=Pig[Start];Pig[Start]:=Pig[i];Pig[i]:=bak;ify>ymthen elseify<ymthen ifx>xmthenSecond:=8elseifx<xmthenSecond:=2elseSecond:=0;if( <>Pig[i].Dir)thenforj:=1toi-1doifRestTime[j]>0if(Pig[j].x=Pig[i].x)and(Pig[j].Dir<> )thenif(Can)and(Second<>0)and(Second<>Pig[i].Dir)thenforj:=1toi-1doifRestTime[j]>tthenCasePig[j].Dirofifyy<1thenyy:=yy+n;ifyy>nthenyy:=yy-if(yy=ym)and(Pig[j].Dir<>Second)thenifCanthen <>0then <>Pig[i].Dirthenforj:=1tototifPig[j].x=Pig[i].xthen elseifSecond<>0thenif(Second<>0)and(Second<>Pig[i].Dir)thenforj:=1totdoMovePigs(i,k,5,0);forj:=1tototdoifPig[j].y=Pig[i].ythenPig[j].Dir:=Second;ifbbthenWhiletot>0doMovePigs(i,k,5,0);ProcedurePrint;Vari:Longint; fori:=1toTimedoCaseStep[i].xofifStep[i].x=5then