{"id":276,"date":"2021-09-08T13:56:48","date_gmt":"2021-09-08T05:56:48","guid":{"rendered":"https:\/\/aisumura.net\/blog\/?p=276"},"modified":"2021-09-20T23:23:29","modified_gmt":"2021-09-20T15:23:29","slug":"uva11495-bubbles-and-buckets","status":"publish","type":"post","link":"https:\/\/aisumura.net\/blog\/2021\/09\/08\/uva11495-bubbles-and-buckets\/","title":{"rendered":"[UVA]11495 Bubbles and Buckets"},"content":{"rendered":"\n<p style=\"font-size:22px\">\u672c\u4eba\u65bc\u8a72blog\u7684\u5168\u90e8\u6587\u7ae0\u8f49\u79fb\u81f3<a href=\"https:\/\/blog.kkwtech.com\/uva\/11536-smallest-sub-array\"><a href=\"https:\/\/blog.kkwtech.com\/uva\/11495-bubbles-and-buckets\">[UVA] 11495 Bubbles and Buckets &#8211; KKWBlog (kkwtech.com)<\/a><\/a>\u8a72\u7db2\u57df\u4e0b\uff0c\u5176\u5f8c\u6b64\u8655\u4e0d\u9032\u884c\u66f4\u65b0\uff0c\u4e00\u5f8b\u65bc\u65b0\u7ad9\u9ede\u66f4\u65b0\u3002<\/p>\n\n\n\n<p><a href=\"https:\/\/zerojudge.tw\/ShowProblem?problemid=d195\">d195. 11495 &#8211; Bubbles and Buckets &#8211; \u9ad8\u4e2d\u751f\u7a0b\u5f0f\u89e3\u984c\u7cfb\u7d71 (zerojudge.tw)<\/a><br><em><strong>\u984c\u76ee\u91cd\u9ede<\/strong><\/em>:<br>\u7d66\u5b9a\u4e00\u6578\u5217\uff0c\u4e26\u4f9d\u7167\u984c\u76ee\u7684\u79fb\u52d5\u898f\u5247(\u50c5\u80fd\u79fb\u52d5\u76f8\u9130\u7684\u6578\u5b57)\u7531\u5c0f\u5230\u5927\u6392\u5e8f\uff0c\u4e26\u8a08\u7b97\u51fa\u4ea4\u63db\u7684\u6b21\u6578\u3002<br><br><em><strong>\u89e3\u984c\u601d\u8def<\/strong><\/em>:<br>\u4e00\u958b\u59cb\u770b\u5230\u9019\u984c\u4ee5\u70ba\u662fBubble sort\u5c31\u80fd\u89e3\u51fa\u4f86\u6b8a\u4e0d\u77e5TLE\uff0c\u9664\u4e86bubble sort\u4e4b\u5916\u7684sort\u53c8\u597d\u50cf\u6c92\u6709\u81e8\u8fd1\u6578\u5b57\u7684\u6bd4\u8f03\uff0c\u53ea\u597d\u7ffb\u89e3\u7b54\uff0c\u7d50\u679c\u53ea\u9700\u8981merge sort\u5c31\u80fd\u89e3\u984c\u4e86\u3002<br>merge sort:<br>\u5c071\u6578\u5217\u62c6\u62102\u500b\u5b50\u6578\u5217\uff0c\u82e52\u500b\u5b50\u6578\u5217\u7121\u6cd5\u7e7c\u7e8c\u62c6\u5247\u505a\u6392\u5e8f\uff0c\u6700\u5f8c\u5c07\u6240\u6709\u5b50\u6578\u5217merge\u8d77\u4f86\uff0c\u6642\u9593\u8907\u96dc\u5ea6N*log(N)\u3002<br>\u800c\u8a72\u6392\u5e8f\u6cd5\u4e2d\u7684\u5176\u4e2d\u4e00\u500b\u908f\u8f2f\u589e\u52a0\u5982\u4e0b<br>\u5b9a\u7fa9:\u7d66\u5b9a2\u5b50\u6578\u5217x,y\u4e26\u5c07\u5176\u5408\u4f75 x:(1, 4, 5) y:(2, 3)<br>1.\u5ba3\u544a\u9663\u5217z\u5b58\u653ex,y\u5408\u4f75\u7684\u6578\u5217(\u5047\u8a2d\u5148\u5c07x\u65bc\u524d,\u65bc\u5f8cy\u653e\u5165\u8a72\u9663\u5217\u5167) z:(1, 4, 5, 2, 3)<br>2.\u6bd4\u8f03x[0],y[0]\uff0c\u8f03\u5c0f\u8005\u653e\u9032x\u5c3e\u7aef\u4e26\u4e14\u8f03\u5c0f\u8005index++ z:(1, 4, 5, 2, 3)<br>3.\u6bd4\u8f03x[1],y[0]\uff0c\u82e5\u9047\u5230\u5f8c\u653e\u5165z\u7684\u6578\u5217\u8f03\u5c0f\u8005\uff0c\u9019\u6642\u5019\u8981\u79fb\u52d5y[0]\u81f3z[1]\uff0c\u984c\u76ee\u9650\u5236\u53ea\u80fd\u9130\u8fd1\u6578\u5b57\u4ea4\u63db\u56e0\u6b64\u9700\u8981\u4ea4\u63db2\u6b21\uff0cy index++ z:(1, 2, 4, 5, 3)<br>\u91cd\u8907\u6b65\u9a5f2,3\u5c31\u80fd\u6392\u5e8f\u5b8c\u4e26\u4e14\u5f97\u5230\u4ea4\u63db\u7684\u6b21\u6578<br><br>\u4e0d\u904e\u5176\u5be6\u53ef\u4ee5\u512a\u5316\uff0c\u4e26\u4e0d\u9700\u8981\u4e00\u958b\u59cb\u5c07x,y\u653e\u5165z\u4e5f\u4e0d\u9700\u8981\u505a\u4ea4\u63db\uff0c\u53ef\u4ee5\u76f4\u63a5\u8a08\u7b97\u51fa\u4ea4\u63db\u6b21\u6578(count)<br>\u516c\u5f0f: <\/p>\n\n\n\n<div class=\"wp-block-katex-display-block katex-eq\" data-katex-display=\"true\"><pre> count = z.midIndex - x.currentIndex + 1\\\\ \nwhere\\ x[currentIndex] &gt; y[currentIndex]\\\\\nProof:\\\\\nz.midIndex = x.lastIndex \\\\\n=&gt; count = x.lastIndex - x.currentIndex + 1\\\\\n\u53c8\u56e0\u4ea4\u63db\u53ea\u6703\u51fa\u73fe\u65bcx &gt; y\u6642\uff0c\u800c\u4ea4\u63db\u6b21\u6578\u7b49\u65bccurrentIndex - targetIndex\uff0c\\\\\n\u4e5f\u5c31\u662findex\u7bc4\u570d\u5167\u7684\u6578-1\uff0c\u53e6\u5916y\u524d\u65b9\u7684\u6578\u5b57\u53ea\u6703\u662fx\u5b50\u6578\u5217\uff0c\u9019\u662f\u6210\u70bay.currentIndex\u7684\u689d\u4ef6\u3002\\\\\n\u56e0\u6b64\u50c5\u9700\u8a08\u7b97\u9084\u672a\u6bd4\u8f03\u7684x\u5b50\u6578\u5217\u7684\u6578\u91cf\u5373\u53ef(\u5df2\u6bd4\u8f03\u7684\u6578\u5b57\u4e0d\u7528\u8a08\u7b97\uff0c\u56e0\u70ba\u6c38\u9060\u5c0f\u65bc\u672a\u6bd4\u8f03\u7684\u6578)<\/pre><\/div>\n\n\n\n<pre title=\"\u7a0b\u5f0f\u78bc\" class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">#include&nbsp;&lt;bits\/stdc++.h&gt;\nusing&nbsp;namespace&nbsp;std;\nint&nbsp;merge(vector&nbsp;&lt;int&gt;&nbsp;&amp;input,int&nbsp;left,int&nbsp;mid,int&nbsp;right)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;vector&nbsp;&lt;int&gt;&nbsp;tmp&nbsp;(right&nbsp;-&nbsp;left&nbsp;+&nbsp;1,&nbsp;0);\/\/\u66ab\u5b58\u65b0\u6392\u5e8f\u7684\u6578\u5217\n&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;count&nbsp;=&nbsp;0;\/\/\u4ea4\u63db\u6b21\u6578\n&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;mLeft&nbsp;=&nbsp;left;\/\/\u5de6\u908a\u5b50\u6578\u5217\u958b\u59cb\u4f4d\u7f6e\n&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;mRight&nbsp;=&nbsp;mid&nbsp;+&nbsp;1;\/\/\u53f3\u908a\u5b50\u6578\u5217\u958b\u59cb\u4f4d\u7f6e\n&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;m&nbsp;=&nbsp;0;\/\/\u66ab\u5b58\u6578\u5217index\n&nbsp;&nbsp;&nbsp;&nbsp;while(mLeft&nbsp;&lt;=&nbsp;mid&nbsp;&amp;&amp;&nbsp;mRight&nbsp;&lt;=&nbsp;right)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(input[mLeft]&nbsp;&lt;&nbsp;input[mRight])&nbsp;{\/\/\u5de6\u5b50\u6578\u5217\u6578\u5b57&nbsp;&lt;&nbsp;\u53f3\u5b50\u6578\u5217\u6578\u5b57\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp[m++]&nbsp;=&nbsp;input[mLeft++];\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if(input[mLeft]&nbsp;&gt;&nbsp;input[mRight])&nbsp;{\/\/\u5de6\u5b50\u6578\u5217\u6578\u5b57&nbsp;&gt;&nbsp;\u53f3\u5b50\u6578\u5217\u6578\u5b57\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp[m++]&nbsp;=&nbsp;input[mRight++];\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;count&nbsp;+=&nbsp;mid&nbsp;-&nbsp;mLeft&nbsp;+&nbsp;1;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;while(mLeft&nbsp;&lt;=&nbsp;mid)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp[m++]&nbsp;=&nbsp;input[mLeft++];\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;while(mRight&nbsp;&lt;=&nbsp;right)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp[m++]&nbsp;=&nbsp;input[mRight++];\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=&nbsp;left;&nbsp;i&nbsp;&lt;=&nbsp;right;&nbsp;i++)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;input[i]&nbsp;=&nbsp;tmp[i&nbsp;-&nbsp;left];\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;count;\n}\nint&nbsp;mergeSort&nbsp;(vector&nbsp;&lt;int&gt;&nbsp;&amp;input,int&nbsp;left,int&nbsp;right)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;count&nbsp;=&nbsp;0;&nbsp;\n&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;mid&nbsp;=&nbsp;(left&nbsp;+&nbsp;right)&nbsp;\/&nbsp;2;\n&nbsp;&nbsp;&nbsp;&nbsp;if(left&nbsp;&lt;&nbsp;right)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;count&nbsp;+=&nbsp;mergeSort(input,&nbsp;left,&nbsp;mid);\/\/\u5de6\u908a\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;count&nbsp;+=&nbsp;mergeSort(input,&nbsp;mid&nbsp;+&nbsp;1,&nbsp;right);\/\/\u53f3\u908a\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;count&nbsp;+=&nbsp;merge(input,left,mid,right);\/\/merge\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;count;\n}\nint&nbsp;main&nbsp;()&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;n&nbsp;=&nbsp;0;\n&nbsp;&nbsp;&nbsp;&nbsp;while(cin&nbsp;&gt;&gt;&nbsp;n)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;vector&nbsp;&lt;int&gt;&nbsp;input;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(n&nbsp;==&nbsp;0)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;n;&nbsp;i++)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;tmp&nbsp;=&nbsp;0;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;tmp;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;input.push_back(tmp);\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mergeSort(input,&nbsp;0,&nbsp;n&nbsp;-&nbsp;1)&nbsp;%&nbsp;2&nbsp;==&nbsp;0&nbsp;?&nbsp;cout&nbsp;&lt;&lt;&nbsp;\"Carlos&nbsp;\"&nbsp;:&nbsp;cout&nbsp;&lt;&lt;&nbsp;\"Marcelo&nbsp;\";\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;endl;\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;\n}<\/code><\/pre>\n\n\n\n<div class=\"wp-block-katex-display-block katex-eq\" data-katex-display=\"true\"><pre>\u6642\u9593\u8907\u96dc\u5ea6:\nmergeSort()=&gt;\nN*log(N)<\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u672c\u4eba\u65bc\u8a72blog\u7684\u5168\u90e8\u6587\u7ae0\u8f49\u79fb\u81f3[UVA] 11495 Bubbles and Buckets &#8211; [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[25],"tags":[26],"_links":{"self":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/276"}],"collection":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/comments?post=276"}],"version-history":[{"count":11,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/276\/revisions"}],"predecessor-version":[{"id":341,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/276\/revisions\/341"}],"wp:attachment":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/media?parent=276"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/categories?post=276"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/tags?post=276"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}