首页 > ACM题库 > HDU-杭电 > HDU 4036-Rolling Hongshu-分治-[解题报告]HOJ
2015
04-15

HDU 4036-Rolling Hongshu-分治-[解题报告]HOJ

Rolling Hongshu

问题描述 :

To see his girl friend, sweet potato has to go over thousands of mountains. What make things worse, many bitter potatoes lives in these mountains. They hate sweet potato because they don’t have girl friends.

In the world of potatoes, friction force does not exist. So the way potatoes travel is very simple: they start with an initial speed, rolling forward and waiting to get to the destination.

Bitter potatoes lived in different places. When sweet potato rolls passing their home, they begin to chase him (surely by rolling with an initial speed). If sweet potato is caught by a bitter potato, his date with girl friend has to be canceled.

Now sweet potato wants to know the minimum initial speed necessary to see his girl friend.

Maze

输入:

First line is an integer T (T ≤ 50), the number of test cases.

At the beginning of each case is three integers, N, M and w, indicate the number of peaks in the mountains, the number of bitter potatoes and the weight of sweet potato separately.

2 ≤ N ≤ 1000, 0 ≤ M ≤ 1000, 0 < w < 100000.

The next N lines each contain a pair of integers. Each pair of integers xi, hi describe a peak. xi is the horizontal distant between sweet potato’s home and the peak. hi is the height of the peak. All xi are different. 0 = x1 < x2 < … < xn ≤ 100000000, -100000000 ≤ hi ≤ 100000000. Between adjacent peaks is a smooth slope. The bitter potatoes are on these slopes.

The following M lines each contain 3 integers. Each triple of integers pi, vi, mi describe a bitter potato. pi is the horizontal distant between his home and sweet potato’s home. vi is his initial speed. mi is his weight. 0 < pi < xn, 0 ≤ vi ≤ 100000000, 0 < mi < 100000

The gravitational constant in potatoes’ world is 20.

Sweet potato’s home is at point (x1, h1). His girl friend lives at point (xn, hn).

输出:

First line is an integer T (T ≤ 50), the number of test cases.

At the beginning of each case is three integers, N, M and w, indicate the number of peaks in the mountains, the number of bitter potatoes and the weight of sweet potato separately.

2 ≤ N ≤ 1000, 0 ≤ M ≤ 1000, 0 < w < 100000.

The next N lines each contain a pair of integers. Each pair of integers xi, hi describe a peak. xi is the horizontal distant between sweet potato’s home and the peak. hi is the height of the peak. All xi are different. 0 = x1 < x2 < … < xn ≤ 100000000, -100000000 ≤ hi ≤ 100000000. Between adjacent peaks is a smooth slope. The bitter potatoes are on these slopes.

The following M lines each contain 3 integers. Each triple of integers pi, vi, mi describe a bitter potato. pi is the horizontal distant between his home and sweet potato’s home. vi is his initial speed. mi is his weight. 0 < pi < xn, 0 ≤ vi ≤ 100000000, 0 < mi < 100000

The gravitational constant in potatoes’ world is 20.

Sweet potato’s home is at point (x1, h1). His girl friend lives at point (xn, hn).

样例输入:

1
6 2 100
0 0
2 5
3 2
4 1
5 3
8 -2
2 15 100
5 11 100

样例输出:

Case 1: 20.62

题目:一个红薯想去见他的女朋友,他要有一个初始速度,才能翻越高山,问罪最小初速度。

分析:物理题,能量守恒 。

            这道题目也是简单题目,按照能量守恒进行求解就没有问题了;

            求出苦土豆到达起点的速度的最大值,并且求出所有山顶到起点的最大速度,取最大即可;

            求解坐标有点麻烦,不过可以直接用比例计算,每次可利用二分优化找到对应的最近的山峰。

说明:(2011-09-19 00:49)。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

typedef struct _point
{
    double x,y,v;
    double HP;
}point;
point Poin[ 1005 ];
point Tudo[ 1005 ];

int search( double X, int H )
{
    int m,l = 1,h = H;
    while ( l < h ) {
        m = (l+h+1)>>1;
        if ( Poin[ m ].x > X )
            h = m-1;
        else l = m;
    }
    return h;
}

int main()
{
    int T,N,M,W;
    scanf("%d",&T);
    for ( int t = 1 ; t <= T ; ++ t ) {
        
        scanf("%d%d%d",&N,&M,&W);
        for ( int i = 1 ; i <= N ; ++ i )
            scanf("%lf%lf",&Poin[ i ].x,&Poin[ i ].y);
        for ( int i = 1 ; i <= M ; ++ i )
            scanf("%lf%lf%d",&Tudo[ i ].x,&Tudo[ i ].v,&W);
            
        for ( int i = 1 ; i <= M ; ++ i ) {
            int s = search( Tudo[ i ].x, N );
            
            if ( Tudo[ i ].x == Poin[ s ].x )
                Tudo[ i ].y = Poin[ s ].y;
            else
                Tudo[ i ].y = Poin[ s ].y + (Poin[ s+1 ].y-Poin[ s ].y)/(Poin[ s+1 ].x-Poin[ s ].x)*(Tudo[ i ].x-Poin[ s ].x);
                
            Tudo[ i ].HP = 40.0*(Tudo[ i ].y-Poin[ 1 ].y) + Tudo[ i ].v*Tudo[ i ].v;
        }
        
        double Max = 0;
        for ( int i = 1 ; i <= M ; ++ i )
            if ( Max < Tudo[ i ].HP ) 
                Max = Tudo[ i ].HP;
                
        for ( int i = 2 ; i <= N ; ++ i ) {
            double HP = 40.0*(Poin[ i ].y-Poin[ 1 ].y);
            if ( Max < HP ) Max = HP;
        }
        
        printf("Case %d: %.2lf\n",t,sqrt(Max));
    }
    return 0;
}

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

参考:http://blog.csdn.net/mobius_strip/article/details/39429693


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。