中兴捧月算法比赛2021 比特派 C：排队（单调栈+二分查找）

﹏ヽ暗。殇╰゛Y 2023-01-19 10:52 7阅读 0赞

### 原题链接 ###

[C：排队][C]

--------------------

### 题目大意 ###

一堆人在排队，每个人都有三个参数：位置、身高、视力。  
小朋友i能看到小朋友j，需要满足2个条件：  
1、j在i的试里范围内，即i和j的位置差的绝对值小于等于i的视力大小。  
2、i和j之间不存在大于等于j身高的人。（联系实际，如果i和j之间有一个高于等于j的人，就会把j挡住，i就看不见j了）  
求每个人能看到几个人（不含自己）。

--------------------

### 思路 ###

暴力做法先循环每一个人，然后对每个人往左往右找能看到几个，但这样 O ( n 2 ) O(n^2) O(n2)肯定会超时，所以我们就得优化。我们可以考虑对于第i个人**往左看**能看到的人一定是一个身高**从左往右降序排列**的，也就是说如果存在一个人j，他的右边有一个人x比他高，那么x右边的所有人都看不到j，j永远不会再被计算上了，因此根据这个**单调的性质**我们可以**用一个单调栈来存储所有可能作为答案的人**。然后根据i这个人的试里大小在单调栈里找他能看到的人的个数即可，因为栈内是单调的，所以可以直接**二分查找**。

因此做法就是先用**结构体**存所有人的信息，然后按照**位置从小到大**排个序，从左往右扫一遍，用一个单调栈来维护。对每个人先在单调栈里二分找到他视力能看到的人的个数（**计算答案**），然后再将栈内所有比i低的人出栈，再将i入栈（**维护单调栈**），再扫下一个即可。  
当然这只找了他左边能看到的人，我们再按**位置从大到小**排一遍，然后再重复上过程找一遍答案，就是右边能看到的人的个数，加到一块就是答案。

--------------------

### AC代码 ###

#include<iostream>
    #include<algorithm>
    using namespace std;
    const int N = 300010;
    
    int stk[N],ans[N],n;	//stk手动栈，存的是p的编号，ans存答案
    struct node{ 
    	int t,d,h,id;	//t是位置，d是视力，h是身高，id是原编号
    }p[N];		//p存所有人
    
    bool cmp1(node a,node b)	//排序1，按位置从小到大排序
    { 
    	return a.t < b.t;
    }
    
    bool cmp2(node a,node b)	//排序2，按位置从大到小排序
    { 
    	return a.t > b.t;
    }
    
    void monostk()		//单调栈
    { 
    	int top = 0; 	//定义栈顶
    	for(int i = 0;i < n;i++)	//循环每一个数
    	{ 
    		if(i)	//从第二个人开始左边才有人
    		{ 
    			int l = 1,r = top;	//stk是从1存到top的，因此二分的左右边界是1和top
    			while(l < r)	//二分查找
    			{ 
    				int mid = (l+r) / 2;
    				if(abs(p[i].t-p[stk[mid]].t) > p[i].d)	//如果i和j的位置差超过了i的视力，就得往右找。注意这里要加abs取绝对值，因为两遍单调栈i和j的相对大小不一样，第一次位置是从小到大，第二次是从大到小
    					l = mid + 1;
    				else
    					r = mid;
    			}
    			ans[p[i].id] += top-l+1;	//原编号的ans加上能看见的人数
    		}
    		while(top && p[stk[top]].h <= p[i].h)	//当栈顶元素的身高小于i时，都不可能作为后面的答案了
    			top--;		//都出栈
    		stk[++top] = i;	//i入栈
    	}
    }
    
    int main()
    { 
    	cin >> n;
    	for(int i = 0;i < n;i++)
    	{ 
    		cin >> p[i].t >> p[i].h >> p[i].d;	//输入
    		p[i].id = i;	//id是原编号
    	}
    	sort(p,p+n,cmp1);
    	monostk();
    	sort(p,p+n,cmp2);
    	monostk();
    	for(int i = 0;i < n;i++)	//输出答案
    		cout << ans[i] << " ";
    
    	return 0;
    }

[C]: https://ac.nowcoder.com/acm/contest/13215/C