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