poj 2128 Highways

真是一道坑爹的题目，题目其实说的不是很清晰。。。

WA了2次。。。

[题意] 在一条单向公路上，有n个村庄，第i个村庄只能到i以后的村庄，而不能到i之前的村庄(因为是单行道)。新村长要建两条新路，使得各个村庄之间都能走通(一条反向的就可以，为什么要建两条？题目说了，只建一条不足矣增加自己的政绩)

[思路] 找出所有路段中最短的，加上原来的总长，就是答案。有一点要注意，题目说两条路的4个端点必须不同，因此要排除端点重合的问题。另外，n=2和n=3是无解的。

我们知道要满足条件，那么我们就必定使1~n有通路，我们可以从1~n修一条路，在从n-3条边选出最短的边就可以了；这里为什么是从n-3条边里选，这里我们要去掉两个端点的边；

例如：n=4 时 4 7 9，这里答案是12而不是11；

#include  <stdio.h>

int main()
{
	int N;	//有N个村庄
	scanf("%d",&N);

	int pos;	//临时保存各个村庄现在的坐标点
	int pre=0;    //临时保存村庄过去的坐标点
	int sum=0;
	int i;
	int minRoad=0x7fffffff;
	int start;
	for(i=2;i<=N;i++)
	{
		//输入每个村庄pos坐标，村庄1的坐标为0
		scanf("%d",&pos);
		sum+=(pos-pre);

		if (i!=2 && i!=N && pos-pre<minRoad)
		{
			minRoad=pos-pre;
			start=i-1;
		}

		pre=pos;
	}
	
	if (N<4)
	{
		printf("0\n");
		return 0;
	}

	printf("%d\n",sum+minRoad);
	//printf("%d %d %d %d\n",start+1,1,N,start);
	printf("%d %d %d %d\n",N,1,start,start+1);   //居然都AC了

	return 0;
}

根本不用sum，本来就会输入总和的：

#include  <stdio.h>

int main()
{
	int N;	//有N个村庄
	scanf("%d",&N);

	int pos;	//临时保存各个村庄现在的坐标点
	int pre=0;    //临时保存村庄过去的坐标点
	int i;
	int minRoad=0x7fffffff;
	int start;
	for(i=2;i<=N;i++)
	{
		//输入每个村庄pos坐标，村庄1的坐标为0
		scanf("%d",&pos);

		if (i!=2 && i!=N && pos-pre<minRoad)
		{
			minRoad=pos-pre;
			start=i-1;
		}

		pre=pos;
	}
	
	if (N<4)
	{
		printf("0\n");
		return 0;
	}

	printf("%d\n",pos+minRoad);
	//printf("%d %d %d %d\n",start+1,1,N,start);
	printf("%d %d %d %d\n",N,1,start,start+1);   //居然都AC了

	return 0;
}