题意：给出一些地标，范围为(-100,000 ≤ xi ≤ 100,000)
有一个人从原点开始走，每分钟走单位为1的路程（这一点题目似乎没有提到过。。。）
问：最多能访问多少个地标
思路：我们把小于0的，跟大于0的分别用两个数组来表示，然后处理两种状况
1.先走右边再走左边
我们先计算出只走右边的ans，更新出最大值
然后再枚举走到右边的某一个位置（每个位置都遍历一遍）
然后再掉头走左边的位置（这个时候就需要用二分来看看再剩下的时间里能走多少个地标）
2.先走左边再走右边，方法同上
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=2e5+10; 5 ll a[maxn],b[maxn]; 6 ll n,tim,limit; 7 ll mx(ll t1,ll t2) 8 { 9 if(t1>t2) return t1; 10 else return t2; 11 } 12 int main() 13 { 14 int num1=0,num2=0; 15 scanf("%lld%lld",&tim,&n); 16 for(int i=1;i<=n;i++){ 17 ll tmp; 18 scanf("%lld",&tmp); 19 if(tmp<0) a[++num1]=-tmp; 20 else b[++num2]=tmp; 21 } 22 sort(a+1,a+1+num1); 23 sort(b+1,b+1+num2); 24 ll ans=0; 25 for(int i=0;i<=num2;i++){ 26 if(b[i]<=tim){ 27 ans=i; 28 } 29 else break; 30 } 31 for(int i=0;i<=num2;i++){ 32 ll tmp1=i; 33 limit=tim-b[i]*2; 34 if(limit<0) break; 35 ll L=0,R=num1; 36 ll tmp2=0; 37 while(L<=R){ 38 ll mid=L+R>>1; 39 if(a[mid]>limit) 40 R=mid-1; 41 else{ 42 L=mid+1; 43 tmp2=mid; 44 } 45 } 46 ans=mx(ans,tmp1+tmp2); 47 } 48 for(int i=1;i<=num1;i++){ 49 if(a[i]<=tim) 50 ans=mx(ans,i); 51 else break; 52 } 53 for(int i=0;i<=num1;i++){ 54 ll tmp1=i; 55 limit=tim-a[i]*2; 56 if(limit<0) break; 57 ll L=0,R=num2; 58 ll tmp2=0; 59 while(L<=R){ 60 ll mid=L+R>>1; 61 if(b[mid]>limit) 62 R=mid-1; 63 else{ 64 L=mid+1; 65 tmp2=mid; 66 } 67 } 68 ans=mx(ans,tmp1+tmp2); 69 } 70 printf("%lld\n",ans); 71 return 0; 72 }
原文：https://www.cnblogs.com/pangbi/p/12696803.html
