题目描述
轩轩和凯凯正在玩一款叫《龙虎斗》的游戏,游戏的棋盘是一条线段,线段上有n个兵营(自左至右编号1∼n),相邻编号的兵营之间相隔 1 厘米,即棋盘为长度为n−1厘米的线段。i号兵营里有ci位工兵。
下面图1为n=6的示例:
图 1. n=6的示例
轩轩在左侧,代表“龙”;凯凯在右侧,代表“虎”。他们以m号兵营作为分界,靠左的工兵属于龙势力,靠右的工兵属于虎势力,而第m号兵营中的工兵很纠结,他们不属于任何一方。
一个兵营的气势为:该兵营中的工兵数×该兵营到m号兵营的距离;参与游戏一方的势力定义为:属于这一方所有兵营的气势之和。
下面图2为n=6,m=4的示例,其中红色为龙方,黄色为虎方:
图 2. n=6,m=4的示例
游戏过程中,某一刻天降神兵,共有s1位工兵突然出现在了p1号兵营。作为轩轩和凯凯的朋友,你知道如果龙虎双方气势差距太悬殊,轩轩和凯凯就不愿意继续玩下去了。为了让游戏继续,你需要选择一个兵营p2,并将你手里的s2 位工兵全部派往兵营p2,使得双方气势差距尽可能小。
注意:你手中的工兵落在哪个兵营,就和该兵营中其他工兵有相同的势力归属(如果落在m号兵营,则不属于任何势力)。
样例
6
2 3 2 3 2 3
4 6 5 2
2
6
1 1 1 1 1 16
5 4 1 1
1
算法
(从前至后枚举每一座兵营) $O(n^2)$
比较龙与虎的气势
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ss[100010]={0};//从左向右第i个兵营里的起始工兵数量
int main()
{
int n;//兵营数量
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>ss[i];
}
ll m;//不属于任何势力的兵营
ll p1;//天降神兵的兵营
ll s1;// 天降神兵的数量
ll s2;//你手里的工兵数量
ll p2;// 你派往的兵营编号
cin>>m>>p1>>s1>>s2;
ll l=0;//龙的气势
ll h=0;//虎的气势
for(ll i=1;i<m;i++)
{
l+=(m-i)*ss[i];//起始时龙的气势
}
for(ll i=m+1;i<=n;i++)
{
h+=(i-m)*ss[i];//起始时虎的气势
}
if(p1<m)//天降神兵在龙方
{
l+=(m-p1)*s1;//天降神兵后龙方的气势
}
if(p1>m)//天降神兵在虎方
{
h+=(p1-m)*s1;//天降神兵后虎方的气势
}
if(p1==m)
{
l=l+0;
h=h+0;
}
ll mmin=m;//最小的i值
ll mmmin=abs(l-h);//最小的气势差
ll lh;//你派兵后的气势差
ll l2;//你派兵后的龙的气势
ll h2;//你派兵后的虎的气势
if(l<h)
{
for(ll i=1;i<m;i++)
{
l2=l+s2*(m-i);
lh=abs(l2-h);
if(lh<mmmin)
{
mmmin=lh;
mmin=i;
}
}
}
if(l>h)
{
for(ll i=m+1;i<=n;i++)
{
h2=h+s2*(i-m);
lh=abs(l-h2);
if(lh<mmmin)
{
mmmin=lh;
mmin=i;
}
}
}
cout<<mmin;
return 0;
}