{"id":352,"date":"2012-05-17T14:45:37","date_gmt":"2012-05-17T06:45:37","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=352"},"modified":"2020-06-06T14:46:09","modified_gmt":"2020-06-06T06:46:09","slug":"%e8%be%93%e6%b2%b9%e7%ae%a1%e9%81%93%e9%97%ae%e9%a2%98","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=352","title":{"rendered":"\u8f93\u6cb9\u7ba1\u9053\u95ee\u9898"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/\/\u8f93\u6cb9\u7ba1\u9053\u95ee\u9898\n \n\u8fd9\u4e2a\u9898\uff0c\u867d\u7136\u8bf4\u7ed9\u51fa\u4e86\u4e95\u7684x,y\u5750\u6807\uff0c\u4f46\u662f\u8981\u4fee\u5efa\u7684\u4e3b\u7ba1\u9053\u5374\u53ea\u662f\u4e00\u6761\u6a2a\u5411\u7684\uff0c\u800c\u4e14\u5176\u4f59\u7ba1\u9053\u4e5f\u53ea\u662f\u5230\u8fd9\u6761\u7ba1\u9053\u7684\u7ad6\u5411\u8ddd\u79bb\u3002\n\u90a3\u4e48\uff0c\u5c31\u8f6c\u6362\u4e3a\u786e\u5b9a\u4e00\u6761\u76f4\u7ebf y = m\uff0c\u4f7f\u5f97\u5176\u5b83\u4e2a\u70b9\u5230\u8fd9\u6761\u76f4\u7ebf\u7684\u8ddd\u79bb\u6700\u591a\u3002\u4e5f\u8bb8\u4e0d\u9700\u8981\u591a\u7684\u63d0\u793a\uff0c\u5927\u5bb6\u7684\u76f4\u89c9\u5c31\u4f1a\u60f3\u5230\u5e94\u8be5\n\u9009\u6240\u6709y\u503c\u7684\u4e2d\u70b9\u3002\u4f46\u662f\uff0c\u8fd9\u4e2a\u7684\u8bc1\u660e\u5374\u4e0d\u662f\u90a3\u4e48\u7684\u660e\u663e\u3002\n \n\u8bc1\u660e\u5982\u4e0b\uff1a\n   \u8bbe\u6240\u6709\u7684y\u503c\u7cfb\u5217\u4e3ay1,y2,...,yn\uff0c\u5e76\u4e14\u5047\u8bbe\u8fd9\u4e2a\u662f\u6309\u9012\u589e\u6392\u5217\u7684\u3002\u6211\u4eec\u8981\u6c42\u7684\u662fSum = \u03a3|yi-m|(1&lt;=i&lt;=n),\n   \n   1\uff09\u663e\u7136\u5047\u5982\u9009\u5c0f\u4e8ey1\u6216\u8005\u5927\u4e8eyn\u7684y=m\u90fd\u4e0d\u4f1a\u6bd4\u9009y1\u6216\u8005yn\u66f4\u597d\u3002\n   2\uff09\u5982\u679c\u9009y1\u6216\u8005yn\uff0c\u90a3\u4e48|y1-m|+|yn-m| = |yn-y1|\u90fd\u662f\u4e00\u6837\u7684\u7ed3\u679c\uff0c\u751a\u81f3\u9009y1\u548cyn\u4e4b\u95f4\u7684\u4efb\u610f\u4e00\u4e2a\u503c\u3002\n   3\uff09\u5982\u6b64\u7ee7\u7eed\u4e0b\u53bb\uff0c\u5bf9\u4e8ey2\u548cyn\uff0c\u4e5f\u67092\uff09\u6240\u63cf\u8ff0\u7684\u6027\u8d28\n   4\uff09\u7ee7\u7eed\u5230\u6700\u540e\uff0c\u53ea\u9700\u8981\u53d6\u6700\u4e2d\u95f4\u4e00\u5bf9\u70b9\u4e4b\u95f4\u7684\u503c\u5373\u53ef\uff0c\u5982\u679cn\u662f\u5947\u6570\uff0c\u90a3\u4e48\u5c31\u662f\u4e2d\u95f4\u7684\u70b9\uff0c\u5982\u679cn\u662f\u5076\u6570\uff0c\u53d6\u4efb\u610f\u4e00\u4e2a\u4e2d\u95f4\n        \u70b9\u90fd\u53ef\u4ee5\u3002\n \n   \u901a\u8fc7\u4e0a\u9762\u8bc1\u660e\uff0c\u6211\u4eec\u53ef\u4ee5\u9009\u53d6\u7b2cy(n\/2 + 1)\u4f5c\u4e3a\u4fee\u5efa\u4e3b\u7ba1\u9053\u7684\u5730\u65b9\u3002\u5f53\u7136\u8fd9\u53ef\u80fd\u662f\u552f\u4e00\u7684\u6700\u4f18\u9009\u62e9\uff0c\u6216\u8005\u65e0\u6570\u4e2a\u6700\u4f18\u9009\u62e9\u4e2d\u7684\u4e00\u4e2a\u3002\n\u90a3\u4e48\u73b0\u5728\u5df2\u7ecf\u8f6c\u6362\u4e3a\u6c42\u4e2d\u4f4d\u6570\u4e86\uff0c\u6c42\u4e2d\u4f4d\u6570\u7684\u529e\u6cd5\u6700\u7b80\u5355\u7684\u662f\u5bf9\u5e8f\u5217\u6392\u5e8f\u7136\u540e\u53d6\u4e2d\u95f4\u7684\u5373\u53ef\u3002\u7b97\u6cd5\u5bfc\u8bba\u4e0a\u6709\u4e00\u79cd\u5e73\u5747\u4ee3\u4ef7O(n)\u7684\u529e\u6cd5\uff0c\n\u601d\u8def\u7c7b\u4f3c\u4e8e\u5feb\u901f\u6392\u5e8f\uff0c\u5feb\u6392\u7684\u6bcf\u4e00\u6b21\u64cd\u4f5c\u90fd\u662f\u5212\u5206\u6570\u7ec4\uff0c\u524d\u5c0f\u540e\u5927\uff0c\u5982\u679c\u6211\u4eec\u4e5f\u8fd9\u4e00\u6b21\u6b21\u53bb\u5212\u5206\u6570\u7ec4\uff0c\u521a\u597d\u8f74\u5143\u7d20\u5904\u4e8e\u6211\u4eec\u8981\u6c42\u7684\u90a3\u4e2a\u4f4d\u7f6e\n\u4e0a\u90a3\u4e48\u5c31\u8fbe\u5230\u6211\u4eec\u7684\u76ee\u7684\u4e86\uff0c\u4e0b\u9762\u7684\u4ee3\u7801\u4e2dSelect\u51fd\u6570\u5c31\u662f\u6c42\u4e00\u4e2a\u6570\u7ec4\u7684\u4e2d\u4f4d\u6570\u3002\n \n \npackage wkx;\n \nimport java.io.IOException;\nimport java.util.ArrayList;\nimport java.util.Collections;\nimport java.util.Iterator;\nimport java.util.List;\nimport java.util.Scanner;\n \npublic class Test {\n \n\tprivate static int randomPartition(int&#91;] data, int beg, int end) {\n\t\tRandom rand = new Random(new Date().getTime());\n\t\tint pos = rand.nextInt(end - beg + 1) + beg;\n\t\tSystem.out.println(\"pos=\" + pos);\n\t\tint t = data&#91;beg];\n\t\tdata&#91;beg] = data&#91;pos];\n\t\tdata&#91;pos] = t;\n \n\t\tint key = data&#91;beg];\n\t\twhile (beg &lt; end) {\n\t\t\twhile (beg &lt; end &amp;&amp; data&#91;end] >= key)\n\t\t\t\tend--;\n\t\t\tdata&#91;beg] = data&#91;end];\n\t\t\twhile (beg &lt; end &amp;&amp; data&#91;beg] &lt;= key)\n\t\t\t\tbeg++;\n\t\t\tdata&#91;end] = data&#91;beg];\n\t\t}\n\t\tdata&#91;beg] = key;\n\t\treturn beg;\n\t}\n \n\tprivate static int select(int&#91;] data, int beg, int end, int k) {\n\t\tif (beg == end)\n\t\t\treturn data&#91;beg];\n\t\tint mid = randomPartition(data, beg, end);\n\t\tint size = mid - beg + 1;\n\t\tif (k &lt;= size)\n\t\t\treturn select(data, beg, mid, k);\n\t\telse\n\t\t\treturn select(data, mid + 1, end, k - size);\n\t}\n \n\tpublic static void main(String&#91;] args) throws IOException {\n\t\tScanner in = new Scanner(System.in);\n\t\twhile (in.hasNextInt()) {\n\t\t\tList&lt;Integer> l=new ArrayList&lt;Integer>();\n\t\t\tint len = in.nextInt();\n\t\t\tfor(int i=0;i&lt;len;i++){\n\t\t\t\tin.nextInt();\n\t\t\t\tl.add(in.nextInt());\n\t\t\t}\n\t\t\tCollections.sort(l);\n\t\t\tint&#91;] data=new int&#91;len];\n\t\t\tint t=0;\n\t\t\tfor(Iterator&lt;Integer>it=l.iterator();it.hasNext();)\n\t\t\t\tdata&#91;t++]=it.next().intValue();\n\t\t\tint m=select(data,0,len-1,len\/2);\n\t\t\tint sum=0;\n\t\t\tfor(int i=0;i&lt;len;i++){\n\t\t\t\tsum+=Math.abs(m-data&#91;i]);\n\t\t\t}\n\t\t\tSystem.out.println(sum);\n\t\t}\n\t}\n \n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-352","post","type-post","status-publish","format-standard","hentry","category-06-03-play-ground"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/352","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=352"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/352\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=352"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=352"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=352"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}