集训队作业the emperors riddleural1144解题报告

1、黄源河题意简述有 N（N=10000）箱黄金，第 i 箱黄金价值为 Ai。要将这 N 箱黄金赏给 M（M=1000）位将军，每人可以得任意箱，但一箱黄金不能分开发。请找出一种分黄金得方案，使将军中获得最多黄金与获得最少黄金之差不超过 K。分析稍加分析可知，这道题是的，N 和 M 还很大，显然不能搜索。由于题目不是要求最优解，而是求出一个近似解就可以了，所以随机化贪心，遗传算法这些近似算法可以派上用场了。本人做这题用了三个不同策略的贪心，下面我分别介绍一下这三个贪心把。贪心一这是最常规，最容易想到的贪心：发牌式贪心。把这 M 箱黄金，从大到小，依次分给黄金最少的人。用堆实现，时间复杂度为O(N+

2、M)logN)。这个贪心主要是应付 K 比较大的数据，效果还比较理想。但是我发现，如果随机生成大规模数据，最优解有很大利率是 1 或 0，而如果 K 也是 1 或 0 的话，这种发牌式贪心常常做不出来。即使改成随机化的，效果仍然不理想。所以有必要针对 K 等于 1 或 0 的情况选择贪心三的贪心策略，这就是的贪心二和贪心二这个贪心策略是专门为 K=1 的情况精心设计的。如果 K=0，则 N 个人都要得到The Emperors Riddle（URAL 1144）解题从大到小拿黄金，拿的时候过他的指标，直至刚好达到他的指标时停止。这个算法也比较容易实现，时间复杂度为 O(NM)。这个贪心可以应付

3、大部分K=1 的情况，但是仍有极个别的过不了，这时三了。要出最后的王牌贪心贪心三这个贪心其实是贪心二的加强版，也是专门应付 Kmax then max:=j; end;i:=0;for j:=1 to max do beginlsmj:=i;if hsj0 then i:=j;end; end;Procedure adjust; vari,j,x:word; beginx:=tr1; i:=1;repeatj:=i shl 1;if jm then break;if (jm)and(nwtrj+1=nwx then break; tri:=trj;i:=j; until false; tri:

4、=x;end;Procedure greedy1;vari,j,l:word; mx:longbegin;for i:=1 to m do tri:=i;fillchar(jn,sizeof(jn),0); fillchar(nw,sizeof(nw),0); sv:=hs;i:=max; repeatwhile svi0 do beginj:=i; l:=svj;inc(nwtr1,j);nx2svj:=jntr1;jntr1:=svj;svj:=nxtsvj; adjust;end; i:=lsmi;until i=0; mx:=0;for i:=1 to m doif nwimx the

5、n mx:=nwi; mine:=mx-nwtr1;end;Procedure greedy2(la,lb:word); vari,j:word;nw:long begin;fillchar(jn,sizeof(jn),0); sv:=hs;for i:=1 to m do beginj:=max; nw:=b; repeatif nw0 do beginif (nw0)or(nw=0);if (nw1)or(nw=0)and(lb=0)or(nw=1)and(la=0) then exit; if nw=0 then dec(lb) else dec(la);end; mine:=b-a;e

6、nd;Procedure greedy3(la,lb:word); vari,j,x,y,z:long begin;fillchar(jn,sizeof(jn),0); sv:=hs;for i:=1 to m do beginfor j:=1 to b do dpj:=30000;dp0:=0;j:=max; repeatif svj0 then beginfor x:=b-1 downto 0 do if dpx30000 then beginy:=x+j; z:=svj;while (z0)and(y0)and(dpa30000) then x:=a; if (lb0)and(dpb30

7、000) then x:=b;if x0 then beginif x=a then dec(la) else dec(lb); repeatnx2svdpx:=jni;jni:=svdpx; svdpx:=nxtsvdpx; dec(x,dpx);until x=0; break;end; end; j:=lsmj;until j=0; end; mine:=b-a;end; BeGiN init;greedy1;if minek then begina:=tot div m; lb:=m div a; b:=succ(a); lb:=tot mod m; la:=m-lb; greedy2(la,lb);if minek then greed