2021年6月上海月赛T5题解(做基础123题时遇到的)

平衡点

内存限制: 256 Mb时间限制: 1000 ms

题目描述

给定一个由 n 个整数组成的数列 a1​,a2​,⋯,an​，请为这个数列找到一个平衡点，使得平衡点左侧与右侧的力矩尽量接近。

若平衡点为 ak​，则左侧力矩定义为数列中下标小于 k 的各个元素到 ak​ 的距离乘以这些元素大小的总和。同理，右侧力矩定义为数列中下标大于 k 的每个元素到 ak​ 的距离乘以这些元素大小的总和。

例如 n=6，若选 a4​ 为平衡，左力矩计算公式为：

L=a1​×(4−1)+a2​×(4−2)+a3​×(4−3)

右力矩计算公式为：

R=a5​×(5−4)+a6​×(6−4)

请找到一个最佳平衡点，并输出选择该点为平衡点时，左右力矩之差绝对值的最小值。

输入格式

第一行：单个整数表示 n；
第二行：n 个整数表示 a1​,a2​,⋯,an​。

输出格式

单个整数：表示在选择了最佳平衡点的前提下，两侧力矩之差绝对值的最小值。

数据范围

• 0≤ai​≤1,000,000；
• 对于 30% 的数据，3≤n≤10,000；
• 对于 60% 的数据，3≤n≤50,000；
• 对于 100% 的数据，3≤n≤300,000。

 这道题等于《龙虎斗》没有天降神兵

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,a[300100],b[300100],ma=4379574354654654;
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		b[i]=b[i-1]+a[i];
	}
	long long l=0,r=0;
	for(int i=2;i<=n;i++)r=r+(i-1)*a[i];
	ma=min(ma,abs(r-l));
	for(int i=2;i<=n;i++){
		l=l+b[i-1];
		r=r-(b[n]-b[i-1]);
		ma=min(ma,abs(r-l));
	}
	cout<<ma;
	return 0;
}