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

Winter_LoL_ · 2024-12-26 20:38:18 · 题解

一道很水的题。

明显不管 p2 位于什么位置，双方的原气势值都不会受到影响。所以可以考虑提前预处理出龙虎双方的气势值，然后枚举 p2，计算出 p2 确定后的气势值后，求所有方案中的双方气势差的最小值所对应的 p2。

预处理时间复杂度 \mathcal{O}(n)，枚举 p2 的时间复杂度也为 \mathcal{O}(n)，总时间复杂度 \mathcal{O}(n)。

Code:

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100010],p1,s1,s2,f[100010],sum1,sum2,minn=INT_MAX,p2,t;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m>>p1>>s1>>s2;
    a[p1]+=s1;//可以直接把s1个工兵放入第p1个兵营
    for(int i=1;i<=n;i++){//预处理
        if(i<m)sum1+=a[i]*abs(i-m);//如果该兵营属于龙方，龙方气势值增加
        else sum2+=a[i]*abs(i-m);//否则虎方气势值增加
        f[i]=s2*abs(i-m);//预处理出把s2个工兵放入第i个兵营会增加的气势值
    }for(int i=1;i<=n;i++){//枚举p2
        if(i<m)t=abs(sum1+f[i]-sum2);//如果该兵营属于龙方，t为龙方气势加上f[i]后与虎方气势的差
        else if(i>m)t=abs(sum2+f[i]-sum1);//否则，t为虎方气势加上f[i]后与龙方气势的差
        else t=abs(sum1-sum2);//不然s2不属于任何势力，t为双方气势差
        if(t<minn){//如果当前方案的结果更优
            minn=t;//更新最小值
            p2=i;//记录答案
        }
    }cout<<p2;
}