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

#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;
}