C++ 拔河比赛队伍分配 - 最优中点算法实现

今天小Q班的体育课，是进行拔河比赛。同学们个个兴奋极了。体育老师- -声令下，就抢着拉绳子与好了位置，谁也不肯让谁。

每位同学都一个力量值, 为了让两边队伍实力均衡，体育老师想找一个合适的“中点”, 将队伍分成两边, 使得两边队伍力量总值相差最小。你来帮体育老师想想办法?

输入

第一行有两个正整数。一个整数N ( 2 <= N <= 500000)，表示小Q班上的人数。 第二行有N个整数，依次表示队伍中每位同学的力量值P(0<=p<= 100000)。

输出

输出两个数x和y。表示在x和y之间设置 “中点”, 可以使队伍两边的力总值相差最小(如果有多个中点，则以x值小的优先)。

思路：

1. 首先读入输入的N和力量值数组P。

2. 计算力量值数组的总和total。

3. 假设中点位置为i，从1到N-1依次遍历。

4. 计算左半边队伍的力量值总和left_sum，初始值为0。

5. 计算右半边队伍的力量值总和right_sum，初始值为total。

6. 遍历数组P，将前i个元素加入left_sum，将剩余的元素加入right_sum。

7. 计算两个队伍力量值总和的差值diff，初始值为|left_sum - right_sum|。

8. 如果diff小于当前最小差值min_diff，则更新min_diff为diff，并更新中点位置为i。

9. 输出中点位置i和i+1。

代码实现：

#include <iostream>
#include <cmath>
using namespace std;
int main() {
int N;
cin >> N;
int P[N];
int total = 0;
for (int i = 0; i < N; i++) {
cin >> P[i];
total += P[i];
}
int left_sum = 0;
int right_sum = total;
int min_diff = abs(left_sum - right_sum);
int mid = 0;
for (int i = 0; i < N - 1; i++) {
left_sum += P[i];
right_sum -= P[i];
int diff = abs(left_sum - right_sum);
if (diff < min_diff) {
min_diff = diff;
mid = i;
}
}
cout << mid + 1 << " " << mid + 2 << endl;
return 0;
}

时间复杂度分析：

遍历力量值数组需要O(N)的时间，因此总的时间复杂度为O(N)。