dia.cpp

给定n 个整数a ,a , ,an 1 2 &#61516 组成的序列

/************************************************************************
*转化为求连续最大子段和最接近l/2，把各个边长乘以2  
*就转化为求连续最大子段和最接近l的问题                 
*************************************************************************/
#include"stdio.h"
#include"fstream"
#include"iostream"
using namespace std;
template<class Type>
Type Abs(Type a)//绝对值
{
	return a>0?a:-a;
}
int main()
{
	freopen("input.txt","r",stdin);//从input.txt里面读入
        freopen("output.txt","w",stdout);//写入output.txt里面
	int i,j,n;
	int l,t;//l:周长,t是临时变量
	int minimum;
	while(scanf("%d",&n)!=EOF)
	{
		int *edge=new int [n+1];
		l=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&edge[i]);
			l+=edge[i];
            edge[i]*=2;//各个边长乘2  便于计算
		}
		edge[n]=0;
		n++;
        i=0;j=1;//init
        t=edge[0];//init
		minimum=Abs(l-t);//init
		while(i<n)
		{
			if(Abs(l-(t+edge[j]))<Abs(l-t))
			{/*如果从i到j+1的子段和更接近l*/
				t+=edge[j];/*子段和加edge[j]*/
				j++;/*j前进一步*/
				if(minimum>Abs(l-t))/*是否更接近*/
				   minimum=Abs(l-t);
			}
			else/*i前进一步 j退一步*/
			{
				t-=(edge[i]+edge[j-1]);
				i++;
				j--;
                                if(minimum>Abs(l-t))/*是否更接近*/
				   minimum=Abs(l-t);
			}
		}
		printf("%d\n",(l-minimum)/2);//output,如果输入是整数则一定是整数。
		delete []edge;
	}
	return 0;
}