656
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;
}
最後更新：2017-04-03 05:39:49