{"id":544,"date":"2017-12-01T23:03:50","date_gmt":"2017-12-01T15:03:50","guid":{"rendered":"https:\/\/www.toodyao.com\/?p=544"},"modified":"2018-01-10T17:08:28","modified_gmt":"2018-01-10T09:08:28","slug":"544","status":"publish","type":"post","link":"https:\/\/www.toodyao.com\/?p=544","title":{"rendered":"POJ 2431 Expedition"},"content":{"rendered":"<p><a style=\"color: #000000;\" href=\"http:\/\/poj.org\/problem?id=2431\">http:\/\/poj.org\/problem?id=2431<\/a><\/p>\n<p><span style=\"font-size: 1rem;\">\u9898\u610f\uff1a\u9a7e\u9a76\u4e00\u8f86\u521d\u59cb\u6cb9\u91cf\u4e3aP\u7684\u8f66\uff0c\u8def\u957fL\uff0c\u4e00\u8def\u6709N\u4e2a\u52a0\u6cb9\u7ad9\uff0c\u5206\u522b\u6709\u6cb9\u91cf\u4e3aAi\uff0c\u8ddd\u7ec8\u70b9Bi\uff0c\u6bcf\u5355\u4f4d\u8ddd\u79bb\u6d88\u80171\u6cb9\u91cf\uff0c\u95ee\u8981\u5230\u7ec8\u70b9\u6700\u5c11\u52a0\u6cb9\u6b21\u6570\uff0c\u65e0\u6cd5\u5230\u8fbe\u7ec8\u70b9\u8f93\u51fa-1<\/span><\/p>\n<p>\u5206\u6790\uff1a\u5f53\u8f66\u8d70\u5230\u6ca1\u6cb9\u7684\u65f6\u5019\uff0c\u4f18\u5148\u9009\u62e9\u4e4b\u524d\u6cb9\u91cf\u6700\u5927\u7684\u52a0\u6cb9\u7ad9\u52a0\u6cb9\uff08\u53ef\u591a\u6b21\uff09\uff0c\u7136\u540e\u7ee7\u7eed\u884c\u9a76\uff0c\u5982\u679c\u4f18\u5148\u961f\u5217\u4e3a\u7a7a\uff0c\u5219\u65e0\u6cd5\u5230\u8fbe\u7ec8\u70b9<\/p>\n<p>\u5c06\u52a0\u6cb9\u7ad9\u8ddd\u7ec8\u70b9\u7684\u8ddd\u79bb\u8f6c\u6362\u4e3a\u8ddd\u8d77\u70b9\u7684\u8ddd\u79bb\uff0c\u5e76\u5c06\u7ec8\u70b9\u770b\u6210\u8ddd\u79bbL\uff0c\u6cb9\u91cf0\u7684\u52a0\u6cb9\u7ad9<\/p>\n<pre class=\"lang:default decode:true \">#include &lt;iostream&gt;\n#include &lt;cstdio&gt;\n#include &lt;cstring&gt;\n#include &lt;queue&gt;\n#include &lt;algorithm&gt;\nusing namespace std;\n\n#define INF 0x3F3F3F3F\n\ntypedef pair&lt;int, int&gt; P;\n\nint main()\n{\n    \/\/ freopen(\"input.txt\", \"r\", stdin);\n    int n, l, p;\n    cin &gt;&gt; n;\n    P a[10010];\n    for(int i = 0; i &lt; n; i++)\n        cin &gt;&gt; a[i].first &gt;&gt; a[i].second;\n    cin &gt;&gt; l &gt;&gt; p;\n    for(int i = 0; i &lt; n; i++)\n        a[i].first = l - a[i].first;\n    sort(a, a+n);\n    \/\/ for(int i = 0; i &lt; n; i++)\n    \/\/  cout &lt;&lt; a[i].first &lt;&lt; endl;\n    priority_queue&lt;int&gt; pri;\n    a[n].first = l;\n    a[n].second = 0;\n    n++;\n    int ans = 0, pos = 0, tank = p;\n    for(int i = 0; i &lt; n; i++)\n    {\n        int d = a[i].first - pos;\n        while(tank - d &lt; 0)\n        {\n            if(pri.empty())\n            {\n                cout &lt;&lt; -1 &lt;&lt; endl;\n                return 0;\n            }\n            else\n            {\n                tank += pri.top();\n                pri.pop();\n                ans++;\n            }\n        }\n        tank -= d;\n        pos = a[i].first;\n        pri.push(a[i].second);\n    }\n    cout &lt;&lt; ans &lt;&lt; endl;\n\n    return 0;\n}\n<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>http:\/\/poj.org\/problem?id=2431 \u9898\u610f\uff1a\u9a7e\u9a76\u4e00\u8f86\u521d\u59cb\u6cb9\u91cf\u4e3aP\u7684\u8f66\uff0c\u8def\u957fL\uff0c\u4e00\u8def\u6709N [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,20],"tags":[29],"class_list":["post-544","post","type-post","status-publish","format-standard","hentry","category-acm","category-poj","tag-29"],"_links":{"self":[{"href":"https:\/\/www.toodyao.com\/index.php?rest_route=\/wp\/v2\/posts\/544","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.toodyao.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.toodyao.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.toodyao.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.toodyao.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=544"}],"version-history":[{"count":3,"href":"https:\/\/www.toodyao.com\/index.php?rest_route=\/wp\/v2\/posts\/544\/revisions"}],"predecessor-version":[{"id":547,"href":"https:\/\/www.toodyao.com\/index.php?rest_route=\/wp\/v2\/posts\/544\/revisions\/547"}],"wp:attachment":[{"href":"https:\/\/www.toodyao.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=544"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.toodyao.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=544"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.toodyao.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=544"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}