210855 平衡点

题目描述

给定一个由 个整数组成的数列 ，请为这个数列找到一个平衡点，使得平衡点左侧与右侧的引力尽量接近。

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

例如 ，若选 为平衡，左侧的引力计算公式为：

右侧引力计算公式为：

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

第一行：单个整数表示 ； 第二行： 个整数表示 。

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

输入样例

4
1 2 3 4

输出样例

0

说明

3号位是平衡点

• ；
• 对于 的数据， ；
• 对于 的数据， ；
• 对于 的数据， 。

[枚举]

C++题解代码

#include <bits/stdc++.h>
using namespace std;

long long a;
long long b[100001];


long long yl(int x, int y) {
  int c = (x+((y-x)/2));
  long long f = 0;
  long long g = 0;
  long long d = 0;
  long long e = 0;
  for (int j = 1; j < c; j++) {
    f += (b[j]*(c-j));
  }
  for (int j = (c+1); j <= a; j++) {
    g += (b[j]*(j-c));
  }
  e = abs((f-g));
  if (e == 0) {
    return 0;
  } else if (x >= y) {
    return e;
  } else if (f > g) {
    d = yl(x, (c-1));
  } else {
    d = yl((c+1), y);
  }
  if (e <= d) {
    return e;
  } else {
    return d;
  }
}

// The main procedure
int main() {
  cin>>a;
  for (int i = 1; i <= a; i++) {
    cin>>b[i];
  }
  cout<<yl(1, a);
  return 0;
}

Blockly题解代码图片