{"id":119800,"date":"2026-10-30T13:16:40","date_gmt":"2026-10-30T05:16:40","guid":{"rendered":"https:\/\/www.wsisp.com\/helps\/119800.html"},"modified":"2026-10-30T13:16:40","modified_gmt":"2026-10-30T05:16:40","slug":"%e9%a2%98%e8%a7%a3%ef%bc%9a%e6%b4%9b%e8%b0%b7-p2879-usaco07jan-tallest-cow-s","status":"publish","type":"post","link":"https:\/\/www.wsisp.com\/helps\/119800.html","title":{"rendered":"\u9898\u89e3\uff1a\u6d1b\u8c37 P2879 [USACO07JAN] Tallest Cow S"},"content":{"rendered":"

\u672c\u6587\u5206\u4eab\u7684\u5fc5\u5237\u9898\u76ee\u662f\u4ece\u84dd\u6865\u4e91\u8bfe\u3001\u6d1b\u8c37\u3001AcWing\u7b49\u77e5\u540d\u5237\u9898\u5e73\u53f0\u7cbe\u5fc3\u6311\u9009\u800c\u6765，\u5e76\u7ed3\u5408\u5404\u5e73\u53f0\u63d0\u4f9b\u7684\u7b97\u6cd5\u6807\u7b7e\u548c\u96be\u5ea6\u7b49\u7ea7\u8fdb\u884c\u4e86\u7cfb\u7edf\u5206\u7c7b\u3002\u9898\u76ee\u6db5\u76d6\u4e86\u4ece\u57fa\u7840\u5230\u8fdb\u9636\u7684\u591a\u79cd\u7b97\u6cd5\u548c\u6570\u636e\u7ed3\u6784，\u65e8\u5728\u4e3a\u4e0d\u540c\u9636\u6bb5\u7684\u7f16\u7a0b\u5b66\u4e60\u8005\u63d0\u4f9b\u4e00\u6761\u6e05\u6670\u3001\u5e73\u7a33\u7684\u5b66\u4e60\u63d0\u5347\u8def\u5f84\u3002<\/p>\n

\u6b22\u8fce\u5927\u5bb6\u8ba2\u9605\u6211\u7684\u4e13\u680f：\u7b97\u6cd5\u9898\u89e3：C++\u4e0ePython\u5b9e\u73b0！<\/p>\n

\u9644\u4e0a\u6c47\u603b\u8d34：\u7b97\u6cd5\u7ade\u8d5b\u5907\u8003\u51b2\u523a\u5fc5\u5237\u9898（C++） | \u6c47\u603b<\/p>\n

\n

\u3010\u9898\u76ee\u6765\u6e90\u3011<\/p>\n

\u6d1b\u8c37：P2879 [USACO07JAN] Tallest Cow S – \u6d1b\u8c37<\/p>\n

\u3010\u9898\u76ee\u63cf\u8ff0\u3011<\/p>\n

FJ \u7684 <\/p>\n

N<\/p>\n

N<\/p>\n

<\/span><\/span>N<\/span><\/span><\/span><\/span><\/span> \u5934\u5976\u725b（<\/p>\n

1<\/p>\n

\u2264<\/p>\n

N<\/p>\n

\u2264<\/p>\n

10<\/p>\n

,<\/p>\n

000<\/p>\n

1 \\\\le N \\\\le 10,000<\/p>\n

<\/span><\/span>1<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>N<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>10<\/span>,<\/span><\/span>000<\/span><\/span><\/span><\/span><\/span>）\u6309\u7f16\u53f7 <\/p>\n

1<\/p>\n

1<\/p>\n

<\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u5230 <\/p>\n

N<\/p>\n

N<\/p>\n

<\/span><\/span>N<\/span><\/span><\/span><\/span><\/span> \u6392\u6210\u4e00\u884c\u3002\u6bcf\u5934\u5976\u725b\u6709\u4e00\u4e2a\u6b63\u6574\u6570\u8868\u793a\u7684\u8eab\u9ad8（\u8fd9\u662f\u4e2a\u79d8\u5bc6）\u3002\u73b0\u5728\u4f60\u53ea\u77e5\u9053\u6700\u9ad8\u5976\u725b\u7684\u8eab\u9ad8 <\/p>\n

H<\/p>\n

H<\/p>\n

<\/span><\/span>H<\/span><\/span><\/span><\/span><\/span>（<\/p>\n

1<\/p>\n

\u2264<\/p>\n

H<\/p>\n

\u2264<\/p>\n

1<\/p>\n

,<\/p>\n

000<\/p>\n

,<\/p>\n

000<\/p>\n

1 \\\\le H \\\\le 1,000,000<\/p>\n

<\/span><\/span>1<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>H<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>1<\/span>,<\/span><\/span>000<\/span>,<\/span><\/span>000<\/span><\/span><\/span><\/span><\/span>），\u4ee5\u53ca\u5b83\u7684\u7f16\u53f7 <\/p>\n

I<\/p>\n

I<\/p>\n

<\/span><\/span>I<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

FJ \u63d0\u4f9b\u4e86 <\/p>\n

R<\/p>\n

R<\/p>\n

<\/span><\/span>R<\/span><\/span><\/span><\/span><\/span> \u6761\u4fe1\u606f（<\/p>\n

0<\/p>\n

\u2264<\/p>\n

R<\/p>\n

\u2264<\/p>\n

10<\/p>\n

,<\/p>\n

000<\/p>\n

0 \\\\le R \\\\le 10,000<\/p>\n

<\/span><\/span>0<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>R<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>10<\/span>,<\/span><\/span>000<\/span><\/span><\/span><\/span><\/span>），\u6bcf\u6761\u4fe1\u606f\u5f62\u5982\u201c\u5976\u725b 17 \u80fd\u770b\u5230\u5976\u725b 34\u201d\u3002\u8fd9\u610f\u5473\u7740\u5976\u725b 34 \u7684\u8eab\u9ad8\u4e0d\u5c0f\u4e8e\u5976\u725b 17 \u7684\u8eab\u9ad8，\u5e76\u4e14\u7f16\u53f7\u5728 17 \u548c 34 \u4e4b\u95f4\u7684\u6240\u6709\u5976\u725b，\u5176\u8eab\u9ad8\u90fd\u4e25\u683c\u5c0f\u4e8e\u5976\u725b 17 \u7684\u8eab\u9ad8\u3002<\/p>\n

\u73b0\u5728\u8bf7\u4f60\u8ba1\u7b97\u51fa\u5bf9\u4e8e\u6bcf\u4e00\u5934\u5976\u725b（\u7f16\u53f7\u4ece <\/p>\n

1<\/p>\n

1<\/p>\n

<\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u5230 <\/p>\n

N<\/p>\n

N<\/p>\n

<\/span><\/span>N<\/span><\/span><\/span><\/span><\/span>），\u5728\u6240\u6709\u7ed9\u5b9a\u4fe1\u606f\u90fd\u6210\u7acb\u7684\u524d\u63d0\u4e0b，\u5b83\u53ef\u80fd\u5177\u6709\u7684\u6700\u5927\u8eab\u9ad8\u3002<\/p>\n

\u9898\u76ee\u4fdd\u8bc1\u4e00\u5b9a\u5b58\u5728\u6ee1\u8db3\u6761\u4ef6\u7684\u89e3\u3002<\/p>\n

\u3010\u8f93\u5165\u3011<\/p>\n

\u7b2c <\/p>\n

1<\/p>\n

1<\/p>\n

<\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u884c：\u56db\u4e2a\u7528\u7a7a\u683c\u5206\u9694\u7684\u6574\u6570：<\/p>\n

N<\/p>\n

N<\/p>\n

<\/span><\/span>N<\/span><\/span><\/span><\/span><\/span>，<\/p>\n

I<\/p>\n

I<\/p>\n

<\/span><\/span>I<\/span><\/span><\/span><\/span><\/span>，<\/p>\n

H<\/p>\n

H<\/p>\n

<\/span><\/span>H<\/span><\/span><\/span><\/span><\/span> \u548c <\/p>\n

R<\/p>\n

R<\/p>\n

<\/span><\/span>R<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

\u7b2c <\/p>\n

2<\/p>\n

2<\/p>\n

<\/span><\/span>2<\/span><\/span><\/span><\/span><\/span> \u5230\u7b2c <\/p>\n

R<\/p>\n

+<\/p>\n

1<\/p>\n

R+1<\/p>\n

<\/span><\/span>R<\/span><\/span>+<\/span><\/span><\/span><\/span>1<\/span><\/span><\/span><\/span><\/span> \u884c：\u6bcf\u884c\u4e24\u4e2a\u4e0d\u540c\u7684\u6574\u6570 <\/p>\n

A<\/p>\n

A<\/p>\n

<\/span><\/span>A<\/span><\/span><\/span><\/span><\/span> \u548c <\/p>\n

B<\/p>\n

B<\/p>\n

<\/span><\/span>B<\/span><\/span><\/span><\/span><\/span>（<\/p>\n

1<\/p>\n

\u2264<\/p>\n

A<\/p>\n

1 \\\\le A<\/p>\n

<\/span><\/span>1<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>A<\/span><\/span><\/span><\/span><\/span>, <\/p>\n

B<\/p>\n

\u2264<\/p>\n

N<\/p>\n

B \\\\le N<\/p>\n

<\/span><\/span>B<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>N<\/span><\/span><\/span><\/span><\/span>），\u8868\u793a\u5976\u725b <\/p>\n

A<\/p>\n

A<\/p>\n

<\/span><\/span>A<\/span><\/span><\/span><\/span><\/span> \u80fd\u770b\u5230\u5976\u725b <\/p>\n

B<\/p>\n

B<\/p>\n

<\/span><\/span>B<\/span><\/span><\/span><\/span><\/span>\u3002<\/p>\n

\u3010\u8f93\u51fa\u3011<\/p>\n

\u5171 <\/p>\n

N<\/p>\n

N<\/p>\n

<\/span><\/span>N<\/span><\/span><\/span><\/span><\/span> \u884c，\u7b2c <\/p>\n

i<\/p>\n

i<\/p>\n

<\/span><\/span>i<\/span><\/span><\/span><\/span><\/span> \u884c\u8f93\u51fa\u5976\u725b <\/p>\n

i<\/p>\n

i<\/p>\n

<\/span><\/span>i<\/span><\/span><\/span><\/span><\/span> \u7684\u6700\u5927\u53ef\u80fd\u8eab\u9ad8\u3002<\/p>\n

\u3010\u8f93\u5165\u6837\u4f8b\u3011<\/p>\n

9 3 5 5
\n1 3
\n5 3
\n4 3
\n3 7
\n9 8<\/p>\n

\u3010\u8f93\u51fa\u6837\u4f8b\u3011<\/p>\n

5
\n4
\n5
\n3
\n4
\n4
\n5
\n5
\n5<\/p>\n

\u3010\u6838\u5fc3\u601d\u60f3\u3011<\/p>\n

  • \n

    \u95ee\u9898\u5206\u6790：\u7ed9\u5b9a <\/p>\n

    N<\/p>\n

    N<\/p>\n

    <\/span><\/span>N<\/span><\/span><\/span><\/span><\/span> \u5934\u5976\u725b\u6392\u6210\u4e00\u884c，\u5df2\u77e5\u6700\u9ad8\u5976\u725b\u7f16\u53f7 <\/p>\n

    I<\/p>\n

    I<\/p>\n

    <\/span><\/span>I<\/span><\/span><\/span><\/span><\/span> \u8eab\u9ad8 <\/p>\n

    H<\/p>\n

    H<\/p>\n

    <\/span><\/span>H<\/span><\/span><\/span><\/span><\/span>，\u4ee5\u53ca <\/p>\n

    R<\/p>\n

    R<\/p>\n

    <\/span><\/span>R<\/span><\/span><\/span><\/span><\/span> \u6761"\u80fd\u770b\u5230"\u4fe1\u606f\u3002\u82e5 <\/p>\n

    A<\/p>\n

    A<\/p>\n

    <\/span><\/span>A<\/span><\/span><\/span><\/span><\/span> \u80fd\u770b\u5230 <\/p>\n

    B<\/p>\n

    B<\/p>\n

    <\/span><\/span>B<\/span><\/span><\/span><\/span><\/span>，\u5219 <\/p>\n

    h<\/p>\n

    e<\/p>\n

    i<\/p>\n

    g<\/p>\n

    h<\/p>\n

    t<\/p>\n

    [<\/p>\n

    B<\/p>\n

    ]<\/p>\n

    \u2265<\/p>\n

    h<\/p>\n

    e<\/p>\n

    i<\/p>\n

    g<\/p>\n

    h<\/p>\n

    t<\/p>\n

    [<\/p>\n

    A<\/p>\n

    ]<\/p>\n

    height[B] \\\\ge height[A]<\/p>\n

    <\/span><\/span>h<\/span>e<\/span>i<\/span>g<\/span>h<\/span>t<\/span>[<\/span>B<\/span>]<\/span><\/span>\u2265<\/span><\/span><\/span><\/span>h<\/span>e<\/span>i<\/span>g<\/span>h<\/span>t<\/span>[<\/span>A<\/span>]<\/span><\/span><\/span><\/span><\/span>，\u4e14 <\/p>\n

    A<\/p>\n

    A<\/p>\n

    <\/span><\/span>A<\/span><\/span><\/span><\/span><\/span> \u4e0e <\/p>\n

    B<\/p>\n

    B<\/p>\n

    <\/span><\/span>B<\/span><\/span><\/span><\/span><\/span> \u4e4b\u95f4\u7684\u6240\u6709\u5976\u725b\u8eab\u9ad8\u4e25\u683c\u5c0f\u4e8e <\/p>\n

    h<\/p>\n

    e<\/p>\n

    i<\/p>\n

    g<\/p>\n

    h<\/p>\n

    t<\/p>\n

    [<\/p>\n

    A<\/p>\n

    ]<\/p>\n

    height[A]<\/p>\n

    <\/span><\/span>h<\/span>e<\/span>i<\/span>g<\/span>h<\/span>t<\/span>[<\/span>A<\/span>]<\/span><\/span><\/span><\/span><\/span>\u3002\u6c42\u6bcf\u5934\u5976\u725b\u7684\u6700\u5927\u53ef\u80fd\u8eab\u9ad8\u3002\u8fd9\u662f\u4e00\u4e2a\u5dee\u5206\u6570\u7ec4 + \u533a\u95f4\u7ea6\u675f\u95ee\u9898，\u5173\u952e\u5728\u4e8e\u5c06"\u80fd\u770b\u5230"\u5173\u7cfb\u8f6c\u5316\u4e3a\u533a\u95f4\u9ad8\u5ea6\u9650\u5236，\u7528\u5dee\u5206\u6570\u7ec4\u9ad8\u6548\u5904\u7406\u3002<\/p>\n<\/li>\n

  • \n

    \u7b97\u6cd5\u9009\u62e9：<\/p>\n