{"id":383,"date":"2023-03-19T18:43:08","date_gmt":"2023-03-19T10:43:08","guid":{"rendered":"https:\/\/www.xgnd.net\/?p=383"},"modified":"2025-11-22T13:08:02","modified_gmt":"2025-11-22T05:08:02","slug":"abc249f-ignore-operations-%e9%a2%98%e8%a7%a3","status":"publish","type":"post","link":"https:\/\/www.xgnd.net\/index.php\/2023\/03\/19\/abc249f-ignore-operations-%e9%a2%98%e8%a7%a3\/","title":{"rendered":"[ABC249F] Ignore Operations \u9898\u89e3"},"content":{"rendered":"<p><a href=\"https:\/\/www.luogu.com.cn\/problem\/AT_abc249_f\">\u9898\u76ee\u4f20\u9001\u95e8<\/a><\/p>\n<h2>\u9898\u610f\u7b80\u8ff0<\/h2>\n<p>\u5b58\u5728\u53d8\u91cf $x$ \uff0c\u521d\u59cb\u65f6 $x=0$ \u3002\u7ed9\u5b9a $n$ \u6b21\u64cd\u4f5c\u6309\u5e8f\u8fdb\u884c\uff0c\u64cd\u4f5c\u7c7b\u578b\u4ee5\u4e0b\u6709\u4e24\u79cd\uff1a<\/p>\n<ul>\n<li><code>&lt;code&gt;1 y&lt;\/code&gt;<\/code> \u8868\u793a\u5c06 $x$ \u8d4b\u503c\u4e3a $y$<\/li>\n<li><code>&lt;code&gt;2 y&lt;\/code&gt;<\/code> \u8868\u793a\u5c06 $x$ \u52a0\u4e0a $y$<\/li>\n<\/ul>\n<p>\u4f60\u53ef\u4ee5\u4ece\u4e2d\u5220\u9664\u4e0d\u8d85\u8fc7 $k$ \u4e2a\u64cd\u4f5c\uff0c\u4f7f\u5f97\u6700\u7ec8\u7684 $x$ \u6700\u5927\uff0c\u8f93\u51fa\u6700\u5927\u503c\u3002<\/p>\n<h2>\u9898\u76ee\u5206\u6790<\/h2>\n<p>\u9996\u5148\u53ef\u4ee5\u53d1\u73b0\uff0c\u5f53\u4e00\u4e2a\u8d4b\u503c\u64cd\u4f5c\u88ab\u4fdd\u7559\u65f6\uff0c\u5bf9\u4e8e\u8fd9\u4e2a\u8d4b\u503c\u64cd\u4f5c\uff0c\u5b83\u524d\u9762\u7684\u64cd\u4f5c\u90fd\u53ef\u4ee5\u5ffd\u7565\uff0c\u53ef\u4ee5\u628a\u5b83\u5f53\u505a\u4e00\u4e2a\u201c\u65b0\u7684\u5f00\u59cb\u201d\uff0c\u5220\u9664\u5b83\u524d\u9762\u7684\u64cd\u4f5c\u662f\u591a\u4f59\u7684\u3002<\/p>\n<p>\u8fd9\u65f6\u6211\u4eec\u53ef\u4ee5\u8003\u8651\u4ece\u540e\u5f80\u524d\u679a\u4e3e\u64cd\u4f5c\uff0c\u56e0\u4e3a\u524d\u9762\u7684\u64cd\u4f5c\u4e0d\u5f71\u54cd\u540e\u9762\u7684\u64cd\u4f5c\uff0c\u4e14\u540e\u9762\u7684\u8d4b\u503c\u548c\u76f8\u52a0\u64cd\u4f5c\u5bf9\u7ed3\u679c\u7684\u5f71\u54cd\u66f4\u5927\u3002<\/p>\n<p>\u4e3a\u4e86\u4f7f\u7ed3\u679c\u5c3d\u53ef\u80fd\u5927\uff0c\u6211\u4eec\u53ef\u4ee5\u8d2a\u5fc3\u9009\u53d6\u76f8\u52a0\u64cd\u4f5c\u4e2d\u5bf9\u7ed3\u679c\u8d1f\u8d21\u732e\u5c3d\u53ef\u80fd\u5c0f\u7684\uff0c\u6b63\u7684\u76f4\u63a5\u8ba1\u5165\u548c\uff0c\u8d1f\u7684\u7528\u4e00\u4e2a\u4f18\u5148\u961f\u5217\u5904\u7406\u5c31\u884c\uff1b\u800c\u5bf9\u4e8e\u8d4b\u503c\u64cd\u4f5c\uff0c\u8ba8\u8bba\u5220\u6216\u4e0d\u5220\u7684\u60c5\u51b5\uff0c\u53d6\u6700\u5927\u503c\u5373\u53ef\uff0c\u5e76\u4e14\u8981\u4fdd\u8bc1\u5728\u5f53\u524d\u8d4b\u503c\u64cd\u4f5c\u540e\u7684\u8d4b\u503c\u64cd\u4f5c\u90fd\u88ab\u5220\u9664\u3002<\/p>\n<h2>Code<\/h2>\n<pre><code class=\"language-cpp\">#include&amp;lt;bits\/stdc++.h&amp;gt;\nusing namespace std;\nconst int maxn=200005;\nint n,k;\nlong long sum,ans=-0x3f3f3f3f3f3f3f;\nint t[maxn],a[maxn];\npriority_queue&amp;lt;int&amp;gt; q;\n\nint main(){\n    ios::sync_with_stdio(0);\n    cin&amp;gt;&amp;gt;n&amp;gt;&amp;gt;k;\n    for(int i=1;i&amp;lt;=n;i++)cin&amp;gt;&amp;gt;t[i]&amp;gt;&amp;gt;a[i];\n\n    for(int i=n;i&amp;gt;=1;i--){\n        if(t[i]==1){\n            ans=max(ans,sum+a[i]);\n            k--;\n            if(k&amp;lt;0)break;\n            while(q.size()&amp;gt;k){   \/\/\u4fdd\u8bc1\u5143\u7d20\u4e2a\u6570\u4e0d\u8d85\u8fc7k\uff0c\u8d85\u8fc7k\u65f6\u5219\u5f39\u51fa\u961f\u9996\n                sum+=q.top();\n                q.pop();\n            }\n        }\n        else{\n            if(a[i]&amp;gt;=0)sum+=a[i];\/\/\u6b63\u7684\u76f4\u63a5\u52a0\u5165\n            else {\n                q.push(a[i]);    \/\/\u8d1f\u7684\u4e22\u8fdb\u4f18\u5148\u961f\u5217\n                while(q.size()&amp;gt;k){\n                    sum+=q.top();\n                    q.pop();\n                }\n            }\n        }\n    }\n    ans=max(ans,sum);\n    cout&amp;lt;&amp;lt;ans&amp;lt;&amp;lt;endl;\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u4f20\u9001\u95e8 \u9898\u610f\u7b80\u8ff0 \u5b58\u5728\u53d8\u91cf $x$ \uff0c\u521d\u59cb\u65f6 $x=0$ \u3002\u7ed9\u5b9a $n$ \u6b21\u64cd\u4f5c\u6309\u5e8f\u8fdb\u884c\uff0c\u64cd\u4f5c\u7c7b\u578b\u4ee5\u4e0b\u6709\u4e24 [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,3,10],"tags":[],"class_list":["post-383","post","type-post","status-publish","format-standard","hentry","category-c","category-oi","category-10"],"_links":{"self":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/383","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/comments?post=383"}],"version-history":[{"count":3,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/383\/revisions"}],"predecessor-version":[{"id":543,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/383\/revisions\/543"}],"wp:attachment":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/media?parent=383"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/categories?post=383"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/tags?post=383"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}