| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
额,好吧,我承认我是水货。题意:一条线段上多个点,求在这些点上连2条线,求这2条线的长度最短,满足:
1:能连2条线且没有点重复,那么点>=4;
2:能制造一个环,那么至少要多出来一段,那么2个点之间最短的再加上总长就是答案了。
示意图:
|———————<——————<—-———-
| |
-----|>----|-->--|---|-->--|-->--|---|->---|
| |
-——————<——-———<———————<———|
当然你也可以这样连,不过这就不是最短了。
|————————————————-———-——————
| |
-----|-----|-----|---|-----|-----|---|-----|
| |
-——————-————-—————————————|
好吧,其他要注意的是:
1:请把数组开大一点,小心RE;
2:min的初值弄大一点,小心wa;
3:注意架桥的位置,不要在第二个或者倒数第二个地方架桥,小心wa;
附件:
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include<algorithm>
#define N 50001
using namespace std;
int s[N];
int main()
{
int n,i,ans,k;
ans=100000001;
scanf("%d",&n);
s[1]=0;
for(i=2;i<=n;i++)
{
scanf("%d",&s[i]);
if(i>2&&i<n&&ans>s[i]-s[i-1])
{
ans=s[i]-s[i-1];
k=i;
}
}
if(n<4)
printf("0\n");
else{
printf("%d\n",ans+s[n]);
printf("%d 1 %d %d\n",k,n,k-1);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator