JZOJ 4821 【NOIP2016提高A组模拟10.15】打膈膜

打膈膜

有$n$个怪物，第$i$个怪物有$h_i$滴血，$DDX$有$m$点魔法值，然后$DDX$和怪物们依次行动，每一回合，$DDX$先行动，然后怪物们再行动。
DDX每次可以选择以下行动之一：

每次行动完后每个存活的怪物都会给$DDX$造成一点伤害，假设$DDX$可以承受足够的伤害，求$DDX$受到伤害的最小值。

数据范围

$n$≤$10^5$，$m$≤$100$，$h_i$≤$10^5$

题解

这题看上去很难，事实上可以用一种十分玄学的方法做——迷之贪心。
首先，按$h_i$从小到大排序。
每次行动若还剩下大于两个的怪物，则用群体攻击，如果只有小于等于两个怪物了，则看此次被攻击的怪物的血量是否为$1$，若为$1$，则用普通攻击把它打死，否则重击它。
直到用到没魔法值了，就一下一下的普通攻击打完怪物即可。

Code(Pascal)

label 123,234;
varans,o,oo:int64;n,m,k,l,i:longint;h:array[0..120000] of int64;
function min(a,b:int64):int64;beginif a>b then exit(A)ELSE EXIT(B);end;
procedure qsort(l,r:longint);vari,j:longint;m:int64;begini:=l;j:=r;m:=h[(l+r) div 2];repeatwhile h[i]<m do inc(i);while h[j]>m do dec(j);if i<=j thenbeginh[0]:=h[i];h[i]:=h[j];h[j]:=h[0];inc(i);dec(j);end;until i>j;if l<j then qsort(l,j);if i<r then qsort(i,r);end;
beginassign(input,'game.in'); reset(input);assign(output,'game.out'); rewrite(output);readln(n,m);for i:=1 to n doread(h[i]);qsort(1,n);l:=1;for i:=1 to m dobeginif l<n-1 thenbegininc(o);while h[l]<=o dobegininc(l);h[l-1]:=0;end;ans:=ans+(n-l+1);oo:=o;endelsebeginh[n-1]:=h[n-1]-o;h[n]:=h[n]-o;O:=0;234:if h[l]=1 thenbeginh[l]:=0;inc(l);if l>n then goto 123;ans:=ans+(n-l+1);goto 234;endelsebegindec(h[l],2);if h[l]=0 then inc(l);if l>n then goto 123;ans:=ans+(n-l+1);end;end;end;if l>=n-1 then oo:=0;if l<=n thenfor i:=l to n doans:=ans+min(0,h[i]-oO)*(n-i+1)-1;123:writeln(ans);
end.