2017计蒜之道初赛第六场-微软大楼设计方案（简单）

近日，微软新大楼的设计方案正在广泛征集中，其中一种方案格外引人注目。在这个方案中，大楼由 $n$ 栋楼组成，这些楼从左至右连成一排，编号依次为 $1$ 到 $n$，其中第 $i$ 栋楼有 h_ih​i​​ 层。每栋楼的每一层为一个独立的 办公区域，可以步行 直达同层相邻楼栋的办公区域，以及 直达同楼栋相邻楼层的办公区域。

由于方案设计巧妙，上一层楼、下一层楼、向左右移动到相邻楼栋同层的办公区域均刚好需要 $1$ 分钟。在这些办公区域中，有一些被 核心部门 占用了（一个办公区域内最多只有一个核心部门），出于工作效率的考虑，微软希望核心部门之间的移动时间越短越好。对于一个给定的 最大移动时间 $k$，大楼的 协同值 定义为：有多少个 核心部门对 之间的移动时间不超过 $k$。由于大楼门禁的限制，不可以走出整个大楼，也不可以登上天台思考人生。你可以认为在办公区域内的移动时间忽略不计，并且在大楼内总是按照最优方案进行移动。

对于一个给定的新大楼设计方案，你能算出方案的协同值么？

输入格式

第一行包含两个正整数 $n,k(1\le k\le 200020)$，分别表示大楼的栋数以及最大移动时间。

第二行包含 $n$ 个正整数 h_1,h_2,...,h_n(1\leq h_i\leq 20)h​1​​,h​2​​,...,h​n​​(1≤h​i​​≤20)，分别表示每栋楼的层数。

接下来一行包含一个正整数 $m$，表示 核心部门 个数。

接下来 $m$ 行，每行两个正整数 x_i,y_i(1\leq x_i\leq n,1\leq y_i\leq h_{x_i})x​i​​,y​i​​(1≤x​i​​≤n,1≤y​i​​≤h​x​i​​​​)，表示该核心部门位于第 x_ix​i​​ 栋楼的第 y_iy​i​​ 层。

输入数据保证 $m$ 个核心部门的位置不会重复。

对于简单版本：$1\le n,m\le 50$；

对于中等版本：$1\le n\le 200000,1\le m\le 2000$；

对于困难版本：$1\le n,m\le 200000$。

输出格式

输出一个整数，即整个大楼的 协同值。

样例解释

样例对应题目描述中的图，核心部门 $1$ 和核心部门 $3$ 之间的距离为 $8>7$，因此不能计入答案。

样例输入

5 7 4 1 1 3 1 3 1 4 3 1 4 3

样例输出

2

题目大意：中文题

解题思路：

枚举每个 核心部门 作为起点，然后 BFS 求出到其它所有核心部门的最短路即可。

时间复杂度 O(mnh+m^2)O(mnh+m​2​​)。

#include<iostream> #include<cstring> #include<string> #include<vector> #include<algorithm> #include<cstdio> #include<map> #include<set> #include<queue> #include<cmath> #include<cctype> #include<cstdlib> #include<list> #include<iomanip> using namespace std; typedef long long LL; const int MAXN=1e3+10; const int INF=0x3f3f3f3f; int G[55][20]; bool vis[55][20]; int h[55]; int dirx[5]={0,0,1,-1}; int diry[5]={1,-1,0,0}; int n,m,k; struct node { int x,y; }dep[55]; struct qnode { int x,y; int c; qnode(int _x,int _y,int _c) { x=_x; y=_y; c=_c; } friend bool operator <(qnode a,qnode b) { return a.c>b.c; } }; int bfs(int sx,int sy,int dx,int dy) { priority_queue<qnode> q; while(!q.empty()) q.pop(); q.push(qnode(sx,sy,0)); vis[sx][sy]=true; while(!q.empty()) { qnode tmp=q.top(); q.pop(); if(tmp.x==dx&&tmp.y==dy) return tmp.c; for(int i=0;i<4;i++) { int tx=tmp.x+dirx[i]; int ty=tmp.y+diry[i]; if(tx<1||tx>n||ty<1||ty>h[tx]) continue; if(G[tx][ty]==0) continue; if(vis[tx][ty]) continue; vis[tx][ty]=true; q.push(qnode(tx,ty,tmp.c+1)); } } return INF; } bool dist(int i,int j) { int sx=dep[i].x; int sy=dep[i].y; int dx=dep[j].x; int dy=dep[j].y; if(bfs(sx,sy,dx,dy)<=k) return true; else return false; } int main() { while(cin>>n>>k) { memset(G,0,sizeof(G)); for(int i=1;i<=n;i++) { cin>>h[i]; for(int j=1;j<=h[i];j++) G[i][j]=1; } // for(int i=1;i<=n;i++) // cout<<h[i]<<endl; cin>>m; for(int i=1;i<=m;i++) { cin>>dep[i].x>>dep[i].y; G[dep[i].x][dep[i].y]=2; } // for(int i=1;i<=m;i++) // { // cout<<dep[i].x<<" "<<dep[i].y<<endl; // } // for(int i=1;i<=n;i++) // { // for(int j=1;j<=5;j++) // { // cout<<G[i][j]; // } // cout<<endl; // } int ans=0; for(int i=1;i<=m;i++) { for(int j=i+1;j<=m;j++) { memset(vis,false,sizeof(vis)); if(dist(i,j)) { //cout<<i<<" "<<j<<endl; ans++; } } } cout<<ans<<endl; } return 0; }