| 题目名称 | 1141. [湖北2011寒假] 求M数 |
|---|---|
| 输入输出 | allm.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 10000 ms (10 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 5 |
| 题目来源 |
 Makazeu
于2012-10-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：102， 提交：212， 通过率：48.11% | ||||
 牧殇 |
100 | 0.325 s | 4.12 MiB | C++ |
 Hzoi_Queuer |
100 | 0.325 s | 4.12 MiB | C++ |
 金身人面兽 |
100 | 0.334 s | 0.32 MiB | C++ |
 SPA |
100 | 0.342 s | 4.13 MiB | C++ |
 lzy |
100 | 0.389 s | 0.31 MiB | C++ |
|
lzy |
100 | 0.397 s | 0.31 MiB | C++ |
 X-man |
100 | 0.407 s | 4.13 MiB | C++ |
 AntiLeaf |
100 | 0.415 s | 0.30 MiB | C++ |
 风吹我已散 |
100 | 0.415 s | 7.92 MiB | C++ |
 lvshoahui |
100 | 0.420 s | 4.10 MiB | C++ |
| 关于 求M数 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
模拟AC
| ||||
|
为什么我的代码得不到满分，请帮助
| ||||
|
| ||||
|
while语句中 要设>=;
数据有-1，所以放弃在栈中先压入一个0的想法吧 。。。  digital-T
2013-04-15 17:21
4楼
| ||||
|
总结：
单调堆栈：栈底：之前的最小（大）元素； 次顶（栈顶紧邻）：最近的较小（大）元素。 单调队列：队头queue.front()：区间内最小（大）元素 次尾（队尾紧邻）：最近的较小（大）元素 | ||||
|
这个题，可以有N种方法来求
1.暴力O(N^2) 不说了... 2.分块O(N*sqrt(N)) 加一个小优化就可以过最极限数据。 3.记忆化剪枝O(？？？) 可以过，时间复杂度在O(N^2)~O(N)，不知道是否有极限数据针对。 4.线段树O(N*log2(N)) 轻松AC 5.单调堆栈O(N) 秒杀  QhelDIV
2012-10-24 23:42
2楼
| ||||
|
题另见：“450.监考老师”
听AT一席话，受益匪浅，可以用“单调堆栈” | ||||
Hzoi_Go灬Fire
zjh
甘罗
Truth.Cirno【题目描述】
n 个数排成一排。一个数的M 数是指的在这个数的左边且比它小的数中最靠近它（即
最靠右）的那个数。依次给出这n 个数，请求出所有这n 个数相对应的M 数。
【输入格式】
从文件allm.in 中读入数据。
数据的第一行是一个正整数n，表示一共有多少个数。
第二行有n 个用空格隔开的正整数，它们从左至右给出了数列中的n 个数。这些数保证
小于2^31。
【输出格式】
输出一行用空格隔开的n 个数到文件allm.out。
这些数对应输入数据中的数的M 数。如果输入中某个数没有M 数（即它左边的数都不
比它小），请输出0。
【样例输入】
7 3 1 2 7 6 7 4
【样例输出】
0 0 1 2 2 6 2
【提示】
对于100%的数据，有n<=1000000.