算法1
(暴力枚举) $O(n^2)$
和上一篇墨守成规差不多,加个拓扑排序就成,此代码照搬上一篇的,ans此篇无用
对于向右的点,能阻挡他的只能是他右下向上的点,或者是他右边和他同向的点
把这些点都找出来,按x升序排序,y降序排,第一个阻挡他就是答案中阻挡他的点
而被他阻挡的也是答案中被他阻挡的(因为是按y降序排的) ;
对于向上的点,由于我们在上一步中已经把阻挡向右的点和被向右的点阻挡的点都处理了
剩下的就是不被阻挡或者是被向上的点阻挡的点,而这些阻拦他的点在他上方
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std ;
const int N = 1e6 + 10 , M = 1010; 、
int n , ans[M] , cnt[N] ;
int ne[N] , e[N] , h[N] , idx , d[N] ;
int add(int a , int b){
d[b] ++ ,e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}
bool cmp1(vector<int>a , vector<int> b){
return (a[0] - b[0]) ? a[0] < b[0] : a[1] > b[1] ;
}
bool cmp2(vector<int>a , vector<int> b){
return (a[1] - b[1]) ? a[1] < b[1] : a[0] < b[0] ;
}
int main()
{
cin >> n ;
vector<vector<int>> a(n , vector<int>(4)) ;
for(int i = 0 ; i < n ; i ++ )
{
char op ; int x , y ;
cin >> op >> x >> y ;
//存坐标, 方向 1向上、0向右,点的输入顺序
a[i][0] = x , a[i][1] = y , a[i][2] = (op == 'E') , a[i][3] = i ;
}
memset(h , -1, sizeof h) ;
memset(ans,0x3f,sizeof ans) ;
sort(a.begin(),a.end(),cmp2) ;
//找向右的点右下角的点
for( int i = 0 ; i < n ; i ++ )
{
if( !a[i][2] ) continue ;
set<int> se ;
vector<vector<int>> b ;
for( int j = 0 ; j < n ; j ++ )
if( a[j][0] > a[i][0] && a[j][1] <= a[i][1] )
b.push_back(a[j]) ;
//按横坐标排序,先阻断的点一定是答案中阻断的点
sort(b.begin() , b.end() , cmp1 ) ;
for( int j = 0 ; j < b.size() ; j ++ )
{
int dx = b[j][0] - a[i][0] , dy = a[i][1] - b[j][1] ;
if( b[j][2] && b[j][1] == a[i][1] )
ans[a[i][3]] = b[j][0] - a[i][0] , add(a[i][3] , b[j][3]) ;
if( !b[j][2] )
{
//向上的点被前面向右的点阻断了 , 或者是向上的点在此阶段同一x出现过了 ;
if( ans[b[j][3]] != 0x3f3f3f3f || se.count(b[j][0])) continue ;
se.insert(b[j][0]) ;
if(dx > dy) ans[a[i][3]] = dx , add(a[i][3], b[j][3]);
if(dx < dy) ans[b[j][3]] = dy , add(b[j][3],a[i][3]);
}
if( ans[a[i][3]] != 0x3f3f3f3f) break ;
}
}
// 向上被同一方向的阻拦
for( int i = 0 ; i < n ; i ++ )
{
if( a[i][2] ) continue ;
int b[2] ; b[1] = 1e9 + 7 ;
for( int j = 0 ; j < n ; j ++ )
//a[j][0] == a[i][0] -> x相同, a[j][2] == 0 -> 向上,最近的
if( !a[j][2] && a[j][1] > a[i][1] && a[j][0] == a[i][0]
&& a[j][1] - a[i][1] < b[1] - a[i][1] )
{
b[0] = a[j][3] , b[1] = a[j][1] ;
//ans[a[i][3]] = min(ans[a[i][3]] , a[j][1] - a[i][1]) ;
}
if( b[1] == 1e9 + 7 ) continue ;
add(a[i][3], b[0]);
}
queue<int> q ;
for( int i = 0 ; i < n ; i ++)
if( !d[i] ) q.push(i) ;
while( q.size() )
{
int u = q.front() ; q.pop() ;
for( int i = h[u] ; i != -1 ; i = ne[i] )
{
int j = e[i] ;
cnt[j] += cnt[u] + 1 ;
if( -- d[j] == 0 )q.push(j) ;
}
}
for( int i = 0 ; i < n ; i ++ ) cout << cnt[i] << endl ;
return 0 ;
}