题解：P5016 [NOIP2018 普及组] 龙虎斗

· · 题解

思路

明显的小暴力做法。

可以两重循环来计算工兵在每个兵营里双方的气势。

时间复杂度简单 N^2，在 N \le 10^5 的情况下 TLE 是常有的事。

这时就要用到一个类似换根 DP 的思想。

注意到在工兵降临之前双方总气势不变，所以可以预处理双方各自的气势，这里同时将 s1 加入 p 兵营方便计算。

代码

a[p]+=s1;
for(i=1;i<=n;i++)
    b[i]=abs(m-i)*a[i];
for(i=1;i<m;i++)
    tig+=b[i];
for(i=m+1;i<=n;i++)
    dra+=b[i];//计算双方总气势

然后就可以愉快统计 s1 名工兵在各个军营里导致的双方气势差了。

代码

for(i=1;i<m;i++)//比较工兵在龙方时的气势 
{
    if(wer>abs(tig+abs(m-i)*s2-dra))
    {
        ans=i;
        wer=abs(tig+abs(m-i)*s2-dra);
    }
}
for(i=m+1;i<=n;i++)//比较工兵在虎方时的气势 
{
    if(wer>abs(dra+abs(m-i)*s2-tig))
    {
        ans=i;
        wer=abs(dra+abs(m-i)*s2-tig);
    }
}

提示

在计算势力差时谨慎操作。

以及总势力在极端情况下会到 10^{14}，注意安全。