2014
01-04

# 机器人的旅行

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

#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树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。