2 条题解
-
1
思路
暴力，O(n)，记得开longlong代码
#include <bits/stdc++.h> #define ll long long using namespace std; ll n,s[100005],m,p,s1,s2,p2; ll minn=1e19; ll sum1,sum2,t1,t2; struct T{ ll ju,re,he; }a[100005];//结构体是真好用 inline ll bijiao(ll x,ll y){ if (x>=y){ return x-y; } else{ return y-x; } }//计算距离 int main(){ cin>>n; for (ll i=1;i<=n;i++) cin>>s[i]; cin>>m>>p>>s1>>s2; for (ll i=1;i<=n;i++){ a[i].re=s[i];//人数 a[i].ju=max(m,i)-min(m,i);//距离 a[i].he=a[i].ju*a[i].re;//气势和 } a[p].he+=s1*a[p].ju; for (ll i=1;i<=n;i++){ if (i<m) sum1+=a[i].he; else sum2+=a[i].he; //计算两方的气势和 } for (ll i=1;i<=n;i++){ t1=sum1,t2=sum2; if (i<m){ t1+=(m-i)*s2; } else if(i>m){ t2+=(i-m)*s2; }//枚举每个点，如果是左t1加，如果是右t2加 ll tmp=bijiao(t1,t2);//调用 if (minn>tmp){ minn=tmp; p2=i; } } cout<<p2; return 0; }精缩
#include <bits/stdc++.h> #define ll long long using namespace std; ll n,s[100005],m,p,s1,s2,p2,minn=1e19,sum1,sum2,t1,t2; struct T{ ll ju,re,he; }a[100005]; inline ll bijiao(ll x,ll y){ if (x>=y)return x-y;else return y-x; } int main(){ cin>>n; for (ll i=1;i<=n;i++) cin>>s[i]; cin>>m>>p>>s1>>s2; for (ll i=1;i<=n;i++){ a[i].re=s[i]; a[i].ju=max(m,i)-min(m,i);a[i].he=a[i].ju*a[i].re; }a[p].he+=(s1*a[p].ju); for (ll i=1;i<=n;i++){ if (i<m)sum1+=a[i].he；else sum2+=a[i].he; } for (ll i=1;i<=n;i++){ t1=sum1;t2=sum2; if (i<m)t1+=(m-i)*s2; else if(i>m)t2+=(i-m)*s2; ll tmp=bijiao(t1,t2); if (minn>tmp)minn=tmp;p2=i; }cout<<p2; return 0; } -
-1
hetao1381161 LV 10 @ 2024-2-6 16:22:09
暴力可以直接过，复杂度O(n)
#include <bits/stdc++.h> #define ll long long //不开long long一场空 using namespace std; int n; ll m,p1,s1,s2,a[1000005],tmp;//tmp作为比较基准,存储两方气势之差 int main(){ ll minx = 1e19,ans,sum1=0,sum2=0,t1,t2;//t1,t2为临时变量 scanf("%d",&n); for (int i = 1; i <= n; i++) scanf("%lld",&a[i]); scanf("%lld%lld%lld%lld",&m,&p1,&s1,&s2); a[p1] += s1; for (int i = 1; i <= n; i++){ if (i < m) sum1 += (m-i)*a[i]; else if (i > m) sum2 += (i-m)*a[i];//预处理,先算出两方势力 } for (int i = 1; i <= n; i++){ t1 = sum1; t2 = sum2; if (i < m) t1 += (m-i)*s2; else if (i > m) t2 += (i-m)*s2;//只用算多出来的部分 tmp = abs(t1-t2); if (minx > tmp){ minx = tmp; ans = i;//比较后更新,没啥好说的 } } printf("%lld",ans); return 0; }
- 1