{"id":164,"date":"2026-03-23T23:05:41","date_gmt":"2026-03-23T15:05:41","guid":{"rendered":"https:\/\/www.heroking2000.com\/?p=164"},"modified":"2026-03-23T23:05:41","modified_gmt":"2026-03-23T15:05:41","slug":"%e6%b4%9b%e8%b0%b7p9937-usaco21open-acowdemia-i-b","status":"publish","type":"post","link":"https:\/\/www.heroking2000.com\/?p=164","title":{"rendered":"\u6d1b\u8c37P9937 [USACO21OPEN] Acowdemia I B"},"content":{"rendered":"\n

\u9898\u76ee\u63cf\u8ff0<\/h2>\n\n\n\n

\u7531\u4e8e\u5bf9\u8ba1\u7b97\u673a\u79d1\u5b66\u7684\u70ed\u7231\uff0c\u4ee5\u53ca\u6709\u671d\u4e00\u65e5\u6210\u4e3a \u300cBessie \u535a\u58eb\u300d\u7684\u8bf1\u60d1\uff0c\u5976\u725b Bessie \u5f00\u59cb\u653b\u8bfb\u8ba1\u7b97\u673a\u79d1\u5b66\u535a\u58eb\u5b66\u4f4d\u3002\u7ecf\u8fc7\u4e00\u6bb5\u65f6\u95f4\u7684\u5b66\u672f\u7814\u7a76\uff0c\u5979\u5df2\u7ecf\u53d1\u8868\u4e86 N<\/em> \u7bc7\u8bba\u6587\uff081\u2264N<\/em>\u2264105\uff09\uff0c\u5e76\u4e14\u5979\u7684\u7b2c i<\/em> \u7bc7\u8bba\u6587\u5f97\u5230\u4e86\u6765\u81ea\u5176\u4ed6\u7814\u7a76\u6587\u732e\u7684 c<\/em>i<\/em>\u200b \u6b21\u5f15\u7528\uff080\u2264c<\/em>i<\/em>\u200b\u2264105\uff09\u3002<\/p>\n\n\n\n

Bessie \u542c\u8bf4\u5b66\u672f\u6210\u5c31\u53ef\u4ee5\u7528 h<\/em> \u6307\u6570\u6765\u8861\u91cf\u3002h<\/em> \u6307\u6570\u7b49\u4e8e\u4f7f\u5f97\u7814\u7a76\u5458\u6709\u81f3\u5c11 h<\/em> \u7bc7\u5f15\u7528\u6b21\u6570\u4e0d\u5c11\u4e8e h<\/em> \u7684\u8bba\u6587\u7684\u6700\u5927\u6574\u6570 h<\/em>\u3002\u4f8b\u5982\uff0c\u5982\u679c\u4e00\u540d\u7814\u7a76\u5458\u6709 4 \u7bc7\u8bba\u6587\uff0c\u5f15\u7528\u6b21\u6570\u5206\u522b\u4e3a (1,100,2,3)\uff0c\u5219 h<\/em> \u6307\u6570\u4e3a 2\uff0c\u7136\u800c\u82e5\u5f15\u7528\u6b21\u6570\u4e3a (1,100,3,3) \u5219 h<\/em> \u6307\u6570\u5c06\u4f1a\u662f 3\u3002<\/p>\n\n\n\n

\u4e3a\u4e86\u63d0\u5347\u5979\u7684 h<\/em> \u6307\u6570\uff0cBessie \u8ba1\u5212\u5199\u4e00\u7bc7\u7efc\u8ff0\uff0c\u5e76\u5f15\u7528\u4e00\u4e9b\u5979\u66fe\u7ecf\u5199\u8fc7\u7684\u8bba\u6587\u3002\u7531\u4e8e\u9875\u6570\u9650\u5236\uff0c\u5979\u81f3\u591a\u53ef\u4ee5\u5728\u8fd9\u7bc7\u7efc\u8ff0\u4e2d\u5f15\u7528 L<\/em> \u7bc7\u8bba\u6587\uff080\u2264L<\/em>\u2264105\uff09\uff0c\u5e76\u4e14\u5979\u53ea\u80fd\u5f15\u7528\u6bcf\u7bc7\u5979\u7684\u8bba\u6587\u81f3\u591a\u4e00\u6b21\u3002<\/p>\n\n\n\n

\u8bf7\u5e2e\u52a9 Bessie \u6c42\u51fa\u5728\u5199\u5b8c\u8fd9\u7bc7\u7efc\u8ff0\u540e\u5979\u53ef\u4ee5\u8fbe\u5230\u7684\u6700\u5927 h<\/em> \u6307\u6570\u3002<\/p>\n\n\n\n

\u6ce8\u610f Bessie \u7684\u5bfc\u5e08\u53ef\u80fd\u4f1a\u544a\u77e5\u5979\u7eaf\u7cb9\u4e3a\u4e86\u63d0\u5347 h<\/em> \u6307\u6570\u800c\u5199\u7efc\u8ff0\u5b58\u5728\u8fdd\u53cd\u5b66\u672f\u9053\u5fb7\u7684\u5acc\u7591\uff1b\u6211\u4eec\u4e0d\u5efa\u8bae\u5176\u4ed6\u5b66\u8005\u6a21\u4eff Bessie \u7684\u884c\u4e3a\u3002<\/p>\n\n\n\n

\u8f93\u5165\u683c\u5f0f<\/h2>\n\n\n\n

\u8f93\u5165\u7684\u7b2c\u4e00\u884c\u5305\u542b N<\/em> \u548c L<\/em>\u3002<\/p>\n\n\n\n

\u7b2c\u4e8c\u884c\u5305\u542b N<\/em> \u4e2a\u7a7a\u683c\u5206\u9694\u7684\u6574\u6570 c<\/em>1\u200b,\u2026,c<\/em>N<\/em>\u200b\u3002<\/p>\n\n\n\n

\u8f93\u51fa\u683c\u5f0f<\/h2>\n\n\n\n

\u8f93\u51fa\u5199\u5b8c\u7efc\u8ff0\u540e Bessie \u53ef\u4ee5\u8fbe\u5230\u7684\u6700\u5927 h<\/em> \u6307\u6570\u3002<\/p>\n\n\n\n

\u8f93\u5165\u8f93\u51fa\u6837\u4f8b<\/h2>\n\n\n\n

\u8f93\u5165 #1<\/strong><\/p>\n\n\n\n

4 0\n1 100 2 3<\/pre>\n\n\n\n
\u8f93\u51fa #1<\/strong><\/p>\n\n\n\n
2<\/pre>\n\n\n\n
\u8f93\u5165 #2<\/strong><\/p>\n\n\n\n
4 1\n1 100 2 3<\/pre>\n\n\n\n
\u8f93\u51fa #2<\/strong><\/p>\n\n\n\n
3<\/pre>\n\n\n\n
\u8bf4\u660e\/\u63d0\u793a<\/h2>\n\n\n\n
\u6837\u4f8b\u89e3\u91ca 1<\/h3>\n\n\n\n
Bessie \u4e0d\u80fd\u5f15\u7528\u4efb\u4f55\u5979\u66fe\u7ecf\u5199\u8fc7\u7684\u8bba\u6587\u3002\u4e0a\u6587\u4e2d\u63d0\u5230\uff0c(1,100,2,3) \u7684 h<\/em> \u6307\u6570\u4e3a 2\u3002<\/p>\n\n\n\n
\u6837\u4f8b\u89e3\u91ca 2<\/h3>\n\n\n\n
\u5982\u679c Bessie \u5f15\u7528\u5979\u7684\u7b2c\u4e09\u7bc7\u8bba\u6587\uff0c\u5f15\u7528\u6570\u4f1a\u53d8\u4e3a (1,100,3,3)\u3002\u4e0a\u6587\u4e2d\u63d0\u5230\uff0c\u8fd9\u4e00\u5f15\u7528\u6570\u7684 h<\/em> \u6307\u6570\u4e3a 3\u3002<\/p>\n\n\n\n
\u6d4b\u8bd5\u70b9\u6027\u8d28<\/h3>\n\n\n\n
    \n
  • \u6d4b\u8bd5\u70b9\u00a01\u22127\u00a0\u6ee1\u8db3\u00a0N<\/em>\u2264100\u3002<\/li>\n\n\n\n
  • \u6d4b\u8bd5\u70b9\u00a08\u221210\u00a0\u6ee1\u8db3\u00a0N<\/em>\u22641000\u3002<\/li>\n\n\n\n
  • \u6d4b\u8bd5\u70b9\u00a011\u221217\u00a0\u6ee1\u8db3\u00a0N<\/em>\u2264105\u3002<\/li>\n<\/ul>\n\n\n\n
    \u3010\u4ee3\u7801\u793a\u4f8b\u3011<\/p>\n\n\n\n
    #include <bits\/stdc++.h>\nusing namespace std;\nint n, m, c[100005];\n\nbool chk(int x) {\n\tint sum = 0;\n\tint mm = m;\n\tfor (int i = 1; i <= n; i++) {\n\t\tif (c[i] >= x)\n\t\t\tsum++;\n\t\tif (c[i] == x - 1 && mm > 0) {\n\t\t\tsum++;\n\t\t\tmm--;\n\t\t}\n\t}\n\treturn sum >= x;\n}\n\nint main() {\n\tcin >> n >> m;\n\tfor (int i = 1; i <= n; i++)\n\t\tcin >> c[i];\n\t\/\/if(m<=n) c[n+1]=m;\n\t\/\/else c[n+1]=n;\n\tint l = 1, r = 1e5, ans = -1;\n\n\twhile (l <= r) {\n\t\tint mid = l + (r - l) \/ 2;\n\t\tif (chk(mid)) {\n\t\t\tl = mid + 1;\n\t\t\tans = mid;\n\t\t} else\n\t\t\tr = mid - 1;\n\t}\n\tcout << ans << endl;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
    \u9898\u76ee\u63cf\u8ff0 \u7531\u4e8e\u5bf9\u8ba1\u7b97\u673a\u79d1\u5b66\u7684\u70ed\u7231\uff0c\u4ee5\u53ca\u6709\u671d\u4e00\u65e5\u6210\u4e3a \u300cBessie \u535a\u58eb\u300d\u7684\u8bf1\u60d1\uff0c\u5976\u725b Bessie \u5f00\u59cb\u653b\u8bfb […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22],"tags":[24,25],"class_list":["post-164","post","type-post","status-publish","format-standard","hentry","category-oi","tag-24","tag-25"],"_links":{"self":[{"href":"https:\/\/www.heroking2000.com\/index.php?rest_route=\/wp\/v2\/posts\/164","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.heroking2000.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.heroking2000.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.heroking2000.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.heroking2000.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=164"}],"version-history":[{"count":1,"href":"https:\/\/www.heroking2000.com\/index.php?rest_route=\/wp\/v2\/posts\/164\/revisions"}],"predecessor-version":[{"id":165,"href":"https:\/\/www.heroking2000.com\/index.php?rest_route=\/wp\/v2\/posts\/164\/revisions\/165"}],"wp:attachment":[{"href":"https:\/\/www.heroking2000.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=164"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.heroking2000.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=164"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.heroking2000.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=164"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}