Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

额,好吧,我承认我是水货。

Posted by 2004140022 at 2015-11-03 11:22:58 on Problem 2128 and last updated at 2015-11-03 11:26:20
题意:一条线段上多个点,求在这些点上连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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator