模拟(80pts)

• 依次枚举s2的降落位置，然后计算左右势力值，保存最优答案

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) //获取初始状态
    {
        cin>>a[i];
    }
    int m,p1,s1,s2;
    cin>>m>>p1>>s1>>s2;
    a[p1]+=s1;
    LL ans=2e18;
    int pos=1;
    for(int i=1;i<=n;i++)
    {
        a[i]+=s2; //累加
        LL left=0; //左边的势力值
        for(int j=1;j<m;j++)
        {
            left+=a[j]*(m-j);
        }
        LL right=0; //右边的势力值
        for(int j=m+1;j<=n;j++)
        {
            right+=a[j]*(j-m);
        }
        LL t=abs(left-right); //计算差值
        if(t<ans) //更新答案
        {
            ans=t;
            pos=i;
        }
        a[i]-=s2; //还原
    }
    cout<<pos;
    return 0;
}

枚举($O(n)$100pts)

• 记录当前影响值，通过枚举位置计算影响值。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long LL;
LL s[N];
LL a[N];
int main()
{
    int n;
    cin>>n;
    LL res=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int m,p1;
    LL s1,s2;
    cin>>m>>p1>>s1>>s2;
    for(int i=1;i<=n;i++) //原始气势差距
    {
        res+=(m-i)*a[i];
    }
    res+=(m-p1)*s1; //s1到p1
    LL ans=1e18; //初始化答案
    int p=0;
    for(int i=1;i<=n;i++) //枚举s2到第i个位置
    {
        if(abs(res+(m-i)*s2)<ans)
        {
            ans=abs(res+(m-i)*s2);
            p=i; //更新距离
        }
    }
    cout<<p;
    return 0;
}