<\/p>\n
\u8bfb\u5165\u4e00\u5217\u6b63\u6570N\uff0ca1, a2, \u2026, aN\uff0c\u4ee5\u53ca\u4e00\u4e2a\u6570F\u3002
\n\u5b9a\u4e49ave(i,j) = ai \u5230 aj \u7684\u5e73\u5747\u503c, \u8981\u6c42 j-i+1 >= k\uff0c
\n\u6c42\u4e00\u4e2a\u6700\u5927\u7684ave\uff08i\uff0cj\uff09<\/p>\n
\u3002\u3002\u6bcf\u6b21\u8be2\u95ee\u56fa\u5b9a\u4e00\u70b9 (x, y) \u4e0e\u4e4b\u524d\u67d0\u70b9\u6240\u5f62\u6210\u76f4\u7ebf\u7684\u6700\u5927\u659c\u7387\u3002
\n\u5355\u8c03\u961f\u5217\u7ef4\u62a4\u4e0b\u51f8\u58f3\u5373\u53ef\uff08x \u5355\u8c03\uff09\u3002<\/p>\n
\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e5) + 9;\r\nint s[N], q[N], cz, op;\r\nint n, k;\r\n\r\nLL det(LL x0, int y0, LL x1, int y1){\r\n return x0*y1 - x1*y0;\r\n}\r\n\r\nint dett(int p0, int p1, int p2){\r\n LL t = det(p1-p0, s[p1]-s[p0], p2-p0, s[p2]-s[p0]);\r\n return t < 0 ? -1 : t > 0;\r\n}\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 while (~scanf("%d %d", &n, &k)){\r\n REP_1(i, n) s[i] = s[i-1] + RD();\r\n\r\n DB z = 0; cz = 0, op = -1; FOR_1(i, k, n){\r\n int ii = i-k;\r\n while (cz < op && dett(q[op-1], q[op], ii) <= 0) --op; q[++op] = ii;\r\n while (cz < op && dett(q[cz], q[cz+1], i) >= 0) ++cz;\r\n checkMax(z, (DB)(s[i] - s[q[cz]] ) \/ (i - q[cz]));\r\n }\r\n OT(z);\r\n }\r\n}\r\n\r\n<\/pre>\nhttp:\/\/www.cnblogs.com\/Free-rein\/archive\/2012\/08\/09\/2630190.html<\/a>
\nhttp:\/\/acm.hust.edu.cn\/vjudge\/problem\/viewSource.action?id=2798173<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"","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":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-988","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-fW","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/988","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=988"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/988\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=988"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=988"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=988"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}