yuzh的博客

❤ ECUST ❤

0%

P2390

发表于 更新于 Valine：

题面

题目背景

改编自USACO2007Nov铜组Exploration

题目描述

贝西在一条道路上旅行，道路上有许多地标，贝西想要在日落之前访问尽可能多的路标。将道路视为一条数轴，贝西从原点出发，道路上有n(1<=n<=50000)个地标，每个地标有一个坐标x[i](-100,000 ≤ xi ≤ 100,000)且地标的坐标各不相同，t(1≤ T ≤1000000000)分钟之后将会日落。

输入格式

第一行：两个整数t,n

第二行至第n+1行：地标的坐标x[i]

输出格式

一个整数，贝西能访问的最多的地标数

输入输出样例

#1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
25 14
16
8
-7
3
10
-15
-17
6
-12
14
-13
2
9
-5
#1
1
8

说明/提示

贝西日落时不用回到原点。

解题思路

代码部分参考@NiveusNix的题解

由题意，想要最快捷地走更多的路，就不能有重复的路，因此分下面四种情况

  1. 从原点一直往右走

  2. 从原点一直往左走

  3. 从原点往左走一段再往右走

  4. 从原点往右走一段再往左走

首先，对输入数据进行排序。

其次，分类讨论：

第一种和第二种情况可以直接模拟过去

第三种和第四种则稍微麻烦一点点，需要使用二分来缩减范围。

  1. 设定二分中点

  2. 算出当前所需要的时间（左边所需要的时间*2 + 右边所需要的时间（另外一种情况结论相反））

  3. 判断范围，继续二分 or 结束二分得出结果

代码如下，含有注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;

long long t,n,s,L[50010],R[50010];//L[]存在原点左边的地标离原点的距离，R[]存在原点右边的地标离原点的距离

int main(){
    cin>>t>>n;
    int ll=0,lr=0,sum=0;//ll是左边最远地标离原点的距离，lr是右边最远地标离原点的距离
    for(int i=1;i<=n;i++)//分类（原点左右）
	{
        cin>>s;
        if(s==0)
		
		{
        	sum=1;
        }
        else if(s>0)
		{
			lr++;
            R[lr]=s;           
        }
        else
		{
			ll++;
            L[ll]=-s;           
        }
    }
    sort(L+1,L+ll+1);
    sort(R+1,R+lr+1);

    long long t3=0,t4=0,mt1=0,mt2=0,mt3=0,mt4=0;//t3是第3种情况的子任务解，t4是第4种情况的子任务解，mt1-4是每种情况的最优解
    for(int i=1;i<=ll;i++){//直接往右走
        if(L[i]<=t){
            mt1+=1;
        }
    }
    for(int i=1;i<=lr;i++){//直接往左走
        if(R[i]<=t){
            mt2+=1;
        }
    }

    long long le,ri,mid;//临时左右分段，和二分中点
    for(int i=1;i<=ll;i++){//先枚举左边，回头向右走的坐标
        le=1;
        ri=lr;
        while(ri>=le){//二分查找向右到达的坐标
            mid=(ri+le)/2;
            t3=L[i]*2+R[mid];//算出当前所需要的时间
    		if(t3>t){
                ri=mid-1;
            }
            else{
                le=mid+1;
            }
        }
        mt3=max(mt3,i+ri);
    }
    for(int i=1;i<=lr;i++){//先枚举右边，回头向左走的坐标
        le=1;
        ri=ll;
        while(ri>=le){//二分查找向左到达的坐标
            mid=(ri+le)/2;
            t4=R[i]*2+L[mid];//算出当前所需要的时间
            if(t4>t){
                ri=mid-1;
            }
            else{
                le=mid+1;
            }
        }
        mt4=max(mt4,i+ri);
    }

    cout<<max(max(mt1,mt2),max(mt3,mt4));
	return 0;
}