微软大楼的设计方案（解题报告）

我就是我 2022-06-13 23:48 156阅读 0赞

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

[![f1b609b22fcbe5df57e016e10b547e39e0becec1.png][]][f1b609b22fcbe5df57e016e10b547e39e0becec1.png]

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

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

### 输入格式 ###

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

第二行包含 nnn 个正整数 h1,h2,...,hn(1≤hi≤20)h\_1,h\_2,...,h\_n(1\\leq h\_i\\leq 20)h1,h2,...,hn(1≤hi≤20)，分别表示每栋楼的层数。

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

接下来 mmm 行，每行两个正整数 xi,yi(1≤xi≤n,1≤yi≤hxi)x\_i,y\_i(1\\leq x\_i\\leq n,1\\leq y\_i\\leq h\_\{x\_i\})xi,yi(1≤xi≤n,1≤yi≤hxi)，表示该核心部门位于第 xix\_ixi 栋楼的第 yiy\_iyi 层。

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

对于简单版本：1≤n,m≤501\\leq n,m\\leq 501≤n,m≤50；

对于中等版本：1≤n≤200000,1≤m≤20001\\leq n\\leq 200000,1\\leq m\\leq 20001≤n≤200000,1≤m≤2000；

对于困难版本：1≤n,m≤2000001\\leq n,m\\leq 2000001≤n,m≤200000。

### 输出格式 ###

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

### 样例解释 ###

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

#### 样例输入 ####

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

#### 样例输出 ####

解题思路：简单版本，暴力枚举即可。

中等版本，考虑特殊情况，如两点直连的距离小于k，则必然不能到达；两点由最低层走最长路径小于等于k，则必然能到达。

package jisuanzhidao.chusai6;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    
    public class Two {
    
    	public static void main(String[] args)throws IOException {
    		// TODO Auto-generated method stub
    		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    		String line=null;
    		line=br.readLine();
    		String [] strss=line.split(" ");
    		int n=Integer.parseInt(strss[0]);
    		int k=Integer.parseInt(strss[1]);
    		line=br.readLine();
    		String [] strsH=line.split(" ");
    		int [] h=new int[n];
    		for(int i=0;i<n;++i){
    			h[i]=Integer.parseInt(strsH[i]);
    		}
    		line=br.readLine();
    		int m=Integer.parseInt(line);
    		int [] x=new int[m];
    		int [] y=new int[m];
    		int i=0;
    		int M=m;
    		while((M--)>0){
    			line=br.readLine();
    			String [] strs=line.split(" ");
    			x[i]=Integer.parseInt(strs[0]);
    			y[i++]=Integer.parseInt(strs[1]);
    		}
    		int ans=0;
    		for(int j=0;j<m;++j){
    			for(int w=j+1;w<m;++w){
    				if(lessThanK(x,y,h,k,j,w)){
    					++ans;
    				}
    			}
    		}
    		System.out.println(ans);
    	}
    	
    	public static boolean lessThanK(int [] x,int [] y,int []h,int k,int start,int end){
    		if((Math.abs(x[start]-x[end])+Math.abs(y[start]-y[end]))>k){
    			return false;
    		}
    		if((Math.abs(x[start]-x[end])+y[start]+y[end]-2)<=k){
    			return true;
    		}
    		else{
    			int s=x[start];
    			int e=x[end];
    			if(s>e){
    				int t=s;
    				s=e;
    				e=t;
    			}
    			int maxH=y[start]<y[end]?y[start]:y[end];
    			for(int Y=maxH;Y>=1;--Y){
    				boolean flag=true;
    				for(int i=s-1;i<e;i++){
    					if(h[i]<Y){
    						flag=false;
    						break;
    					}
    				}
    				if(flag){
    					maxH=Y;
    					break;
    				}
    			}
    			int xlen=Math.abs(x[start]-x[end])+1;
    			int ylen=y[start]-maxH+y[end]-maxH;
    			if((xlen+ylen-1)<=k){
    				return true;
    			}
    			else{
    				return false;
    			}
    			
    		}
    	}
    
    }

[f1b609b22fcbe5df57e016e10b547e39e0becec1.png]: /images/20220614/2a41e4b403954b1285974bcde2dd1b84.png