深度优先

这个家伙好懒，除了文章什么都没留下

0%

【算法】微软大楼设计方案

发表于 分类于
本文字数： 4.8k 阅读时长 ≈ 4 分钟

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

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

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

输入格式

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

第二行包含 n_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_，表示 核心部门 个数。

接下来 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_i_x_​i​​ 栋楼的第 y_i_y_​i​​ 层。

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

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

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

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

输出格式

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

样例解释

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

样例输入

1
2
3
4
5
6
5 7
4 1 1 3 1
3
1 4
3 1
4 3

样例输出

1
2

第一题：简单

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
/**
* 
*/
package D6;

import java.util.Scanner;

/**
 * @作者： gx_143
 * @创建时间： 2017-6-4下午07:21:26
 */
public class T2 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		int[] data=new int[n+1];
		for (int i = 1; i < data.length; i++) {
			data[i]=sc.nextInt();
		}
		
		int m=sc.nextInt();
		int[][] arr=new int[m][2];
		for (int i = 0; i < arr.length; i++) {
			arr[i][0]=sc.nextInt();
			arr[i][1]=sc.nextInt();
		}
		int ans=0;
		for (int i = 0; i < arr.length; i++) {
			for (int j = i+1; j < arr.length; j++) {
				
				int a=Math.max(arr[i][0], arr[j][0]);
				int b=Math.min(arr[i][0], arr[j][0]);
				int min=Integer.MAX_VALUE;
				for (int l = b+1; l < a; l++) {
					if(data[l]<min)
						min=data[l];
				}
				if(min>arr[i][1]) min=arr[i][1];
				if(min>arr[j][1]) min=arr[j][1];
				//System.out.println(min+"...");
				int sum=(arr[i][1]-min)+(arr[j][1]-min);
				sum+=Math.abs(arr[i][0]-arr[j][0]);
				//System.out.println(sum);
				if(sum<=k)
					ans++;
			}
		}
		System.out.println(ans);
	}
}

第二题：中等

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 /**
 * 
 */
package D6;

import java.util.Scanner;

/**
 * @作者： gx_143
 * @创建时间： 2017-6-4下午07:15:26
 */
public class T3 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		int[] data=new int[n+1];
		for (int i = 1; i < data.length; i++) {
			data[i]=sc.nextInt();
		}
		
		int m=sc.nextInt();
		int[][] arr=new int[m][2];
		for (int i = 0; i < arr.length; i++) {
			arr[i][0]=sc.nextInt();
			arr[i][1]=sc.nextInt();
		}
		arr=Sort(arr);
		int[][] h=new int[n+1][21];
		for (int i = 1; i < h.length; i++) {
			for (int j = 1; j < 21; j++) {
				if(j!=data[i]){
					h[i][j]=h[i-1][j];
				}else{
					h[i][j]=h[i-1][j]+1;
				}
			}
		}
//		for (int i = 0; i < h.length; i++) {
//			for (int j = 0; j < 21; j++) {
//				System.out.print(h[i][j]+" ");
//			}
//			System.out.println();
//		}
		int ans=0;
		for (int i = 0; i < arr.length; i++) {
			for (int j = i+1; j < arr.length; j++) {
				
				if(arr[j][0]-arr[i][0]>k) break;
				if(Math.abs(arr[j][1]-arr[i][1])>k) continue;
				
				int a= arr[j][0];
				int b= arr[i][0];
				
				int min=0;
				for (int l = 1; l < 21; l++) {
					if(h[b][l]<h[a][l]){
						min=l;
						break;
					}
				}
				//System.out.println(min+"..");
				
				if(min>arr[i][1]) min=arr[i][1];
				if(min>arr[j][1]) min=arr[j][1];
				
				//System.out.println(min+"...");
				int sum=(arr[i][1]-min)+(arr[j][1]-min);
				sum+=Math.abs(arr[i][0]-arr[j][0]);
				//System.out.println(sum);
				if(sum<=k)
					ans++;
			}
		}
		System.out.println(ans);
	}

	/**
	 * @param arr
	 * @return
	 */
	private static int[][] Sort(int[][] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = i+1; j < arr.length; j++) {
				if(arr[i][0]>arr[j][0]){
					int t=arr[i][0];
					arr[i][0]=arr[j][0];
					arr[j][0]=t;
					
					int p=arr[i][1];
					arr[i][1]=arr[j][1];
					arr[j][1]=p;
				}
			}
		}
		return arr;
	}
}

第三题：困难

ps:不会写

题解：

微软大楼设计方案

命题人：陈松扬

简单

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

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

中等

对于两个核心部门 A,B_A_,B，不妨设 x_A\leq x_B_x_​A​​≤x​B​​，那么有 dis(A,B)=x_B-x_A+y_A+y_B_d__i__s_(A,B)=x​B​​−x​A​​+y​A​​+y​B​​ -2\min(h_{x_A},h_{x_A+1},…,h_{x_B}, y_A, y_B)−2min(h​x​A​​​​,h​x​A​​+1​​,…,h​x​B​​​​,y​A​​,y​B​​)。

枚举两个核心部门，那么瓶颈在于快速计算某个区间内 h_h_ 的最小值。注意到 h\leq 20_h_≤20，设 s[i][j]s[i][j]表示前 i_i_ 个位置中有多少 h_h_ 为 j_j_，那么从小到大枚举 j_j_ 即可得到最小值，每次查询复杂度为 O(h)O(h)。

时间复杂度 O(nh+m^2h)O(n__h+m​2​​h)。

困难

还是假设 x_A\leq x_B_x_​A​​≤x​B​​，考虑从左往右枚举 B_B_，用一个单调上升的栈维护 h_h_，那么对于当前的 B_B_ 来说，单调栈按 h_h_ 的区间最小值将序列划分成了 O(h)O(h) 个子区间。

枚举每个子区间，再枚举 y_A_y_​A​​ 的值，那么此时 x_A_x_​A​​ 的取值范围可以直接通过解不等式得到，用前缀和询问出该范围内有多少核心部门即可。

时间复杂度 O(nh^2)O(_n__h_​2​​)。

由于测试数据的覆盖能力有限，出现了一些能通过大规模数据但不能通过小规模数据的情况，这说明写出的代码仍然是有问题的，再仔细检查一下代码。