Visit
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 629 Accepted Submission(s): 248
Problem Description Wangye is interested in traveling. One day, he want to make a visit to some
different places in a line. There are N(1 <= N <= 2000) places located at points x1, x2, ..., xN (-100,000 ≤ xi ≤ 100,000). Wangye starts at HDU (x = 0), and he travels 1 distance unit in 1 minute . He want to know how many places he could visit at most, if he has T (1 <= T <= 200000 ) minutes.
Input 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.
Output For each test case, you should print the number of places,Wangye could visit at most, in one line.
Sample Input
5 16
-3
-7
1
10
8
Sample Output
4
Hint
In the sample, Wangye could visit (-3) first, then goes back to (0), which costs him 6 minutes.
Then he visits (1), (8), (10). So he could visit 4 places at most in 16 minutes. :
Author zjt
題目大意:
給你N個坐标,初始的時候主人公位于點0處,所有點位于坐标軸上,問在時間T限制内,最多能夠通路多少個點。一秒鐘移動一個機關距離。
思路:
1、首先将N個點的坐标進行排序,然後設定l【】,表示坐标為負數的集合,設定r【】,表示坐标為正的集合,對應l【i】<l【i+1】(按照排序處理),同理r【i】<r【i+1】。
2、然後,暴力處理,不難分析出其有兩種走法:
①選一個點,作為走到的左邊的最遠點,然後折返 ,向右走到時間耗用結束為止,維護過程中,最大值。
②選一個點,作為走到的右邊的最遠點,然後折返,向左走到時間耗用結束為止,維護過程中,最大值。
3、輸出最大值即可。預估時間複雜度:O(n^2);
Ac代碼:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[20000];
int l[20000];
int r[20000];
int main()
{
int n,tt;
while(~scanf("%d%d",&n,&tt))
{
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
int contl=0;
int contr=0;
for(int i=0;i<n;i++)
{
if(a[i]<0)
{
l[contl++]=a[i];
}
else r[contr++]=a[i];
}
int output=0;
for(int i=0;i<contl;i++)
{
int tmp=contl-i;
int time=tt+2*l[i];
if(time<0)continue;
for(int j=0;j<contr;j++)
{
int use=0;
if(j==0)use=r[j];
else use=r[j]-r[j-1];
if(time>0&&use<=time)
{
time-=use;
tmp++;
}
else break;
}
output=max(output,tmp);
}
for(int i=0;i<contr;i++)
{
int tmp=i+1;
int time=tt-r[i]*2;
if(time<0)continue;
for(int j=contl-1;j>=0;j--)
{
int use=l[j+1]-l[j];
if(time>0&&time>=use)
{
time-=use;
tmp++;
}
else break;
}
output=max(output,tmp);
}
printf("%d\n",output);
}
}