问题 B: 奶牛排队
时间限制: 1 Sec 内存限制: 128 MB
提交: 13 解决: 9
[提交][状态][讨论版][命题人:add_wjl][Edit] [TestData]
题目链接：http://acm.ocrosoft.com/problem.php?cid=1689&pid=1
题目描述
每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别. 注意: 在最大数据上, 输入和输出将占用大部分运行时间.
输入
* 第一行: N 和 Q. * 第2..N+1行: 第i+1行是第i头牛的身高.
* 第N+2..N+Q+1行: 两个整数, A 和 B (1 <= A <= B <= N), 表示从A到B的所有牛.
输出
*第1..Q行: 所有询问的回答 (最高和最低的牛的身高差), 每行一个.
样例输入
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
196 3 1 7 3 4 2 5 1 5 4 6 2 2
样例输出
复制代码
1
2
3
4
5
6
76 3 0
思路：建一个dp[i][j],i表示从i的位置开始扫描，j表示从i开始（i也包括）往后扫描（1<<j）个数
然后直接RMQ算法，输出的时候优化一下就行了。
代码：
复制代码
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135#include<bits/stdc++.h> using namespace std; int n; int dp_max[100005][30];//动态规划 ，dp[i][j],j的意思是1<<j(扫描的个数)！！ j的意思是1<<j(扫描的个数)！！ j的意思是1<<j(扫描的个数)！！ 重要的事情说3遍！！！ int dp_min[100005][30]; int a[100005];//用于存储数字 void st_max(int m)//初始化dp { for (int i = 1; i <= m; i++) { dp_max[i][0] = a[i];//j位置为0时，相当于1<<0=1,所以在范围为1的区间里的最值就是a[i] } for (int j = 1; (1 << j) <= m; j++) { for (int i = 1; i + (1 << j) - 1 <= m; i++) { dp_max[i][j] = max(dp_max[i][j - 1], dp_max[i + (1 << (j - 1))][j - 1]); //这里不太好解释，就是比如i到i+(1<<j)-1个数分为2组，一组是i到 i+(1<<(j-1))-1，另一组是 i+(1<<(j-1))到i+(1<<j)-1，进行动态规划 } } } int rmq_max(int l, int r)//取l到r区间里的最值 { int k = 0; while ((1 << (k + 1)) <= r - l + 1)k++;//找到某个k可以让2块长为（1<<k）的区间将l到r的区间完全覆盖 return max(dp_max[l][ k], dp_max[r- (1 << k)+1][ k]);//取最值 } void st_min(int m)//和上面几乎一样 { for (int i = 1; i <= m; i++) { dp_min[i][0] = a[i]; } for (int j = 1; (1 << j) <= m; j++) { for (int i = 1; i + (1 << j)-1 <= m; i++) { dp_min[i][j] = min(dp_min[i][j - 1], dp_min[i + (1 << (j - 1))][j - 1]); } } } int rmq_min(int l, int r) { int k = 0; while ((1 << (k + 1)) <= r-l+1)k++; return min(dp_min[l][k], dp_min[r - (1 << (k)) + 1][k]); } int main() { int n; scanf("%d", &n); int k; scanf("%d", &k); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } st_max(n); st_min(n); for(int i=1;i<=k;i++)//套板子即可 { int xx,yy; scanf("%d%d",&xx,&yy); printf("%dn",rmq_max(xx,yy)-rmq_min(xx,yy)); //cout<<rmq_max(xx,yy)<<endl; } }
最后
以上就是威武项链最近收集整理的关于问题 B: 奶牛排队的全部内容，更多相关问题内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复