首页 > ACM题库 > HDU-杭电 > HDU 4723-How Long Do You Have to Draw-贪心-[解题报告]HOJ
2015
09-17

HDU 4723-How Long Do You Have to Draw-贪心-[解题报告]HOJ

How Long Do You Have to Draw

问题描述 :

There are two horizontal lines on the XoY plane. One is y1 = a, the other is y2 = b(a < b). On line y1, there are N points from left to right, the x-coordinate of which are x = c1, c2, … , cN (c1 < c2 < … < cN) respectively. And there are also M points on line y2 from left to right. The x-coordinate of the M points are x = d1, d2, … dM (d1 < d2 < … < dM) respectively.
Now you can draw segments between the points on y1 and y2 by some segments. Each segment should exactly connect one point on y1 with one point on y2.
The segments cannot cross with each other. By doing so, these segments, along with y1 and y2, can form some triangles, which have positive areas and have no segments inside them.
The problem is, to get as much triangles as possible, what is the minimum sum of the length of these segments you draw?

输入:

The first line has a number T (T <= 20) , indicating the number of test cases.
For each test case, first line has two numbers a and b (0 <= a, b <= 104), which is the position of y1 and y2.
The second line has two numbers N and M (1 <= N, M <= 105), which is the number of points on y1 and y2.
The third line has N numbers c1, c2, …. , cN(0 <= ci < ci+1 <= 106), which is the x-coordinate of the N points on line y1.
The fourth line has M numbers d1, d2, … , dM(0 <= di < di+1 <= 106), which is the x-coordinate of the M points on line y2.

输出:

The first line has a number T (T <= 20) , indicating the number of test cases.
For each test case, first line has two numbers a and b (0 <= a, b <= 104), which is the position of y1 and y2.
The second line has two numbers N and M (1 <= N, M <= 105), which is the number of points on y1 and y2.
The third line has N numbers c1, c2, …. , cN(0 <= ci < ci+1 <= 106), which is the x-coordinate of the N points on line y1.
The fourth line has M numbers d1, d2, … , dM(0 <= di < di+1 <= 106), which is the x-coordinate of the M points on line y2.

样例输入:

1
0 1
2 3
1 3
0 2 4

样例输出:

Case #1: 5.66

题目

题意:

两条平行线,各有n、m个点。要连一些线,两个端点分别是两条平行线上的点,并且不能交叉。在取得最多三角形的情况下,求最小的总的线的长度。

题解:

贪心的策略:从左往右,记l和r为两条平行线第一个没被选的点。计算选l或选r新增的线的长度,选最小的。

不能严谨地证明,但是画个图感觉是挺对的。

//Time:265ms
//Memory:1080KB
//Length:953B
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
#define MAXN 100010
#define EPS 1e-8
int x[2][MAXN];
double cal(int l,int r,int len)
{
    len=abs(len);
    return sqrt(len*1.0*len+(x[1][r]-x[0][l])*1.0*(x[1][r]-x[0][l]));
}
int main()
{
    //freopen("/home/moor/Code/input","r",stdin);
    int ncase,n,m,a,b;
    scanf("%d",&ncase);
    for(int hh=1;hh<=ncase;++hh)
    {
        printf("Case #%d: ",hh);
        scanf("%d%d%d%d",&a,&b,&n,&m);
        double ans=0;
        for(int i=0;i<n;++i)    scanf("%d",&x[0][i]);
        for(int i=0;i<m;++i)    scanf("%d",&x[1][i]);
        ans=cal(0,0,b-a);
        for(int l=1,r=1;l<n||r<m;)
        {
            double t1=1e50,t2=1e50;
            if(r!=m)    t2=cal(l-1,r,b-a);
            if(l!=n)    t1=cal(l,r-1,b-a);
            if(t1<t2-EPS)   ans+=t1,++l;
            else    ans+=t2,++r;
        }

        printf("%.2f\n",ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/tri_integral/article/details/11617771