跳至内容
璟雯院
珺璟如晔,雯华若锦
用户工具
登录
站点工具
搜索
工具
显示页面
修订记录
反向链接
最近更改
媒体管理器
网站地图
登录
>
最近更改
媒体管理器
网站地图
您在这里:
start
»
icpc
»
problems
»
luogup1886
icpc:problems:luogup1886
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
====== 滑动窗口 ====== ===== 想法 ===== 维护单调队列,当元素超过区间或元素的值没有竞争力时出队。 ===== 代码实现 ===== <code c++> #include <cstdio> #include <cstring> const int N = 1e6 + 10; int line[N], qu[N], sit[N], head = 0, last = -1; int main() { int n, k; scanf("%d %d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &line[i]); for (int i = 1; i <= n; i++) { while (head <= last && qu[last] >= line[i]) last--; qu[++last] = line[i]; sit[last] = i; while (head <= last && sit[head] < i - k + 1) head++; if (i >= k) { printf("%d ", qu[head]); } } head = 0; last = -1; memset(qu, 0, sizeof(qu)); memset(sit, 0, sizeof(sit)); printf("\n"); for (int i = 1; i <= n; i++) { while (head <= last && qu[last] <= line[i]) last--; qu[++last] = line[i]; sit[last] = i; while (head <= last && sit[head] < i - k + 1) head++; if (i >= k) { printf("%d ", qu[head]); } } return 0; } </code>
/app/www/public/data/pages/icpc/problems/luogup1886.txt
· 最后更改: 2024/03/27 02:53 由
温婕莺
页面工具
显示页面
修订记录
反向链接
回到顶部