{"id":607,"date":"2010-12-25T15:59:57","date_gmt":"2010-12-25T07:59:57","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=607"},"modified":"2012-12-25T16:03:47","modified_gmt":"2012-12-25T08:03:47","slug":"poj-2823-sliding-window","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/poj-2823-sliding-window\/","title":{"rendered":"POJ 2823. Sliding Window"},"content":{"rendered":"

Brief description: <\/h3>\n

\u3002\u3002\u7ef4\u62a4\u4e00\u4e2a\u5bbd\u5ea6\u4e3a k \u7684\u6ed1\u52a8\u7a97\u53e3\u3002\u3002\u5206\u522b\u7edf\u8ba1\u6240\u6709\u4f4d\u7f6e\u7684\u6700\u5927\u503c\u548c\u6700\u5c0f\u503c\u3002\u3002<\/p>\n

<\/p>\n

Analysis: <\/h3>\n

1. C++ \u600e\u4e48\u90fd\u8fc7\u3002 \/ G++ \u600e\u4e48\u90fd TLE \u3002\u3002
\n2. \u201c\u90a3\u4e9b500-600MS\u7684\u4ee3\u7801\u5230\u5e95\u662f\u600e\u4e48\u5f04\u51fa\u6765\u7684\u3002\u3002\u201d\u3002\u3002
\n.. .<\/p>\n

\r\nconst int N = 1000009;\r\n\r\nint a[N], q[N], cz, op;\r\nint n, k;\r\n\r\ntemplate<class T> void gao(T cmp){\r\n\r\n    cz = 0, op = -1; REP_1(i, k){\r\n        while (cz <= op && cmp(a[i], a[q[op]])) --op;\r\n        q[++op] = i;\r\n    }\r\n\r\n    printf("%d ", a[q[cz]]);\r\n\r\n    FOR_1(i, k + 1, n){\r\n        if (q[cz] == i - k) ++cz;\r\n        while (cz <= op && cmp(a[i], a[q[op]])) --op;\r\n        q[++op] = i; printf("%d ", a[q[cz]]);\r\n\r\n    }\r\n\r\n    puts("");\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    RD(n, k); REP_1(i, n) RD(a[i]);\r\n    gao(less<int>()), gao(greater<int>());\r\n}\r\n<\/pre>\n
External link: <\/h3>\n
http:\/\/acm.hust.edu.cn:8080\/judge\/problem\/viewProblem.action?id=16694<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Brief description: \u3002\u3002\u7ef4\u62a4\u4e00\u4e2a\u5bbd\u5ea6\u4e3a k \u7684\u6ed1\u52a8\u7a97\u53e3\u3002\u3002\u5206\u522b\u7edf\u8ba1\u6240\u6709\u4f4d\u7f6e\u7684\u6700\u5927\u503c\u548c\u6700\u5c0f\u503c\u3002\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[47],"tags":[73],"class_list":["post-607","post","type-post","status-publish","format-standard","hentry","category-hdu","tag-73"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-9N","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/607","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=607"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/607\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=607"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=607"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=607"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}