拔河比赛(解决方案)

题目描述

今天小Q班的体育课，是进行拔河比赛。同学们个个兴奋极了。体育老师一声令下，就抢着拉绳子占好了位置，谁也不肯让谁。 
每位同学都一个力量值，为了让两边队伍实力均衡，体育老师想找一个合适的“中点”，将队伍分成两边，使得两个队伍力量总值相差最小。你来帮体育老师想想办法？

输入

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

输出

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

样例输入

10
65 50 80 85 120 95 85 55 75 120

样例输出

5 6

提示

前5个人的力量和为400，后5个人的力量和为430，最小差值为30。
数据范围:
对于60%的数据    N<10000;
对于100%的数据  N<500000；

代码如下：

#include
using namespace std;
int a[1001000];
int b[1001000];
int main()
{
	long long n;
	cin>>n;
	long long sum=0;
	for(long long i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	long long number=0;
	for(long long i=1;i<=n;i++)
	{	number+=a[i];
		b[i]=abs(sum-number-number);
	}
	long long min,location;
	min=b[1];location=1;long long i;
	for(i=1;i=b[i])
		{
			min=b[i];
			location=i;
		}
	}
	cout< 
1，解决了队伍中存在力量值为零的问题。（某些思路会受数字零的存在而被影响）。
 
2，找到合适的问题切入思路，否则思路的选择会影响整个题实现的难易程度。
 
3，核心部分仅进行一次循环，找到当前位置下力量值的差异，存入另外的数组当中，在稍后进行比较筛选即可。
 
4，注意数值的大小，int类型会溢出，可以用longlong进行存取。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5635240.html