题目描述
样例
算法1
(暴力枚举) $O(n)$
水题不水啊
坑点:
1.爆$int$,开$long long$
2.注意暴力时不要枚举一次就重新计算气势值,这样会超时
时间复杂度
$O(N)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define ll long long
#define re register
ll a[N];//num of bing
int main(){
ll n,m,p1,s1,s2,ls=0,hs=0;
scanf("%lld",&n);
for(re ll i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
scanf("%lld%lld%lld%lld",&m,&p1,&s1,&s2);
a[p1]+=s1;
for(re ll i=1;i<m;++i){
ls+=a[i]*(m-i);
}
for(re ll i=m+1;i<=n;++i){
hs+=a[i]*(i-m);
}
long long mini=0,minn=LLONG_MAX;
for(re ll i=1;i<=n;++i){
if(i<m){
if(abs(ls+s2*(m-i)-hs)<minn){
minn=abs(ls+s2*(m-i)-hs);
mini=i;
}
}
if(i==m){
if(abs(ls-hs)<minn){//不要写成加号
minn=abs(ls-hs);//不要写成加号
mini=i;
}
}
if(i>m){
if(abs(hs+s2*(i-m)-ls)<minn){
minn=abs(hs+s2*(i-m)-ls);
mini=i;
}
}
}
cout<<mini<<endl;
return 0;
}