首页 > ACM题库 > HDU-杭电 > hdu 2233 机器人的旅行[解题报告]C++
2014
01-04

hdu 2233 机器人的旅行[解题报告]C++

机器人的旅行

问题描述 :

一天机器人小A在做HDOJ的2217这个题目,题目的描述是一个喜欢旅行的人类一条成直线的旅行线路上旅行,这条旅行线路上有N(1<=N<=2000)个旅行点分别座落在x1,x2,…,xN(-100,000<=xi<=100,000)上,然后这个人类从x=0处出发,他每走1单位的距离耗时1分钟,他想知道用T(1<=T<=200000)分钟他最多能到达过多少个旅行点。作为机器人的的小A觉得自己有充足的体能可以让旅行点更多(1<=N<=100000),这些旅行点坐落的更分散(xi在int范围)以及更长的时间(T在int范围),在这些条件下他想知道他能最多到达多少个旅行点。

输入:

The input contains several test cases .Each test case starts with two number N and T which indicate the number of places and the time respectively. Then N lines follows, each line has a number xi indicate the position of i-th place.

输出:

The input contains several test cases .Each test case starts with two number N and T which indicate the number of places and the time respectively. Then N lines follows, each line has a number xi indicate the position of i-th place.

样例输入:

5 16
-3
-7
1
10
8

样例输出:

4


题意:给出一些观光点的坐标,求在规定的时间内最多能浏览多少景点。
思路:枚举可能的情况,选出最大的值。因为最多折返一次(即从正到负或从负到正)。按照样例来说:走到“1”处,反方向走;走到“8”处,反方向走,走到“10”处反方向走;走到-3处,反方向走………….找出最大的浏览景点。 测试数据有些水…..

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define INF 0x7FFFFFFF
using namespace std;
int point[100005];
int main()
{
    int n,t,i,j;
    while(scanf("%d%d",&n,&t) != EOF)
    {
        int sum1=0,sum2=0,tmp=0,max1=-INF,max2=-INF,tt=0;
        for(i=0; i<n; i++)
        {
            scanf("%d",&point[i]);
        }
        sort(point,point+n);//排好序
        for(i=0; i<n; i++)
        {
            if(point[i] >=0 && point[i] <= t)//正向走多少点,对应反向能走多少点
            {
                tt++;
                sum1 = tt;
                tmp = t - point[i];
                for(int j=n-1;  j>=0; j--)
                {
                    if(point[j] < 0 && abs(2*point[j]) <=tmp)//2*point[j] 正反两次
                        sum1++;
                }
            }
            if(max1 < sum1 )//找最大的sum1
                max1 = sum1;
        }
        tt = 0;
        for(i=n-1; i>=0; i--)//与上面对应
        {
            if(point[i] <=0 && abs(point[i]) <= t)//反向走几个点,对应正向走多少
            {
                tt++;
                sum2 = tt;
                tmp = t - abs(point[i]);
                for(int j=0; j<n; j++)
                {
                    if(point[j] > 0 && 2*point[j] <=tmp)
                        sum2++;
                }
            }
            if(sum2 > max2)//找最大的sum2
                max2 = sum2;
        }
       // printf("%d %d\n",max1,max2);
        printf("%d\n",max1>max2?max1:max2);//输出最大
    }
    return 0;
}

 


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。