{"id":249,"date":"2026-08-01T11:52:05","date_gmt":"2026-08-01T03:52:05","guid":{"rendered":"https:\/\/huxiaole.cloud\/?p=249"},"modified":"2026-08-01T11:56:09","modified_gmt":"2026-08-01T03:56:09","slug":"k-%e7%82%b9%e7%9b%b4%e5%be%84","status":"publish","type":"post","link":"https:\/\/huxiaole.cloud\/index.php\/2026\/08\/01\/k-%e7%82%b9%e7%9b%b4%e5%be%84\/","title":{"rendered":"K. \u70b9\u76f4\u5f84"},"content":{"rendered":"\n<h1 class=\"wp-block-heading\">K. \u70b9\u76f4\u5f84<\/h1>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u6bcf\u6b21\u6d4b\u8bd5\u65f6\u95f4\u9650\u5236\uff1a3 \u79d2<\/li>\n\n\n\n<li>\u5185\u5b58\u9650\u5236\uff1a256 MB<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">\u9898\u76ee\u63cf\u8ff0<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u4f50\u7f57\u53c8\u5728\u67d0\u4e2a\u5e73\u5766\u7684\u5c0f\u5c9b\u4e0a\u8ff7\u8def\u4e86\uff0c\u5c9b\u4e0a\u6709 $n$ \u4e2a\u5730\u6807\u3002\u5c71\u6cbb\u6c14\u574f\u4e86\uff0c\u60f3\u7528\u5730\u56fe\u7ed9\u4ed6\u6307\u8def\u3002\u7b2c $i$ \u4e2a\u5730\u6807\u7684\u5750\u6807\u4e3a $(x_i, y_i)$\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e3a\u4e86\u7167\u987e\u4f50\u7f57\u7cdf\u7cd5\u7684\u65b9\u5411\u611f\uff0c\u5c71\u6cbb\u51b3\u5b9a\u4ece\u5730\u56fe\u4e0a<strong>\u6700\u591a\u64e6\u9664\u4e24\u4e2a<\/strong>\u5730\u6807\u3002\u5730\u56fe\u7684\u201c\u8ff7\u5931\u76f4\u5f84\u201d\u5b9a\u4e49\u4e3a\u5269\u4f59\u5730\u6807\u4e2d\u4efb\u610f\u4e24\u70b9\u4e4b\u95f4\u7684\u6700\u5927\u66fc\u54c8\u987f\u8ddd\u79bb\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e24\u70b9 $(x_1, y_1)$ \u548c $(x_2, y_2)$ \u4e4b\u95f4\u7684\u66fc\u54c8\u987f\u8ddd\u79bb\u4e3a $|x_1 &#8211; x_2| + |y_1 &#8211; y_2|$\u3002\u5982\u679c\u5269\u4f59\u5730\u6807\u5c11\u4e8e\u4e24\u4e2a\uff0c\u5219\u76f4\u5f84\u4e3a $0$\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6c42\u5c71\u6cbb\u5728\u6700\u591a\u64e6\u9664\u4e24\u4e2a\u5730\u6807\u540e\uff0c\u80fd\u8fbe\u5230\u7684\u6700\u5c0f\u53ef\u80fd\u76f4\u5f84\u3002<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u5165\u683c\u5f0f<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u7b2c\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u6574\u6570 $t$\uff08$1 \\le t \\le 10^4$\uff09\u2014\u2014 \u6d4b\u8bd5\u7528\u4f8b\u6570\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u7684\u7b2c\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u6574\u6570 $n$\uff08$1 \\le n \\le 2 \\times 10^5$\uff09\u2014\u2014 \u70b9\u7684\u6570\u91cf\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u63a5\u4e0b\u6765 $n$ \u884c\uff0c\u6bcf\u884c\u5305\u542b\u4e24\u4e2a\u6574\u6570 $x_i$ \u548c $y_i$\uff08$-10^9 \\le x_i, y_i \\le 10^9$\uff09\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4fdd\u8bc1\u6240\u6709\u6d4b\u8bd5\u7528\u4f8b\u7684 $n$ \u4e4b\u548c\u4e0d\u8d85\u8fc7 $2 \\times 10^5$\u3002<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u51fa\u683c\u5f0f<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u5bf9\u4e8e\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u8f93\u51fa\u4e00\u4e2a\u6574\u6570 \u2014\u2014 \u6700\u5c0f\u7684\u53ef\u80fd\u76f4\u5f84\u3002<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u793a\u4f8b<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u8f93\u5165<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>2\n3\n0 0\n10 0\n0 10\n4\n0 0\n2 0\n0 2\n2 2<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u8f93\u51fa<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>0\n2<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u793a\u4f8b\u8bf4\u660e<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u7b2c\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u4e2d\uff0c\u64e6\u9664 $(10,0)$ \u548c $(0,10)$\uff0c\u53ea\u5269\u4e00\u4e2a\u70b9\uff0c\u76f4\u5f84\u4e3a $0$\u3002<\/li>\n\n\n\n<li>\u7b2c\u4e8c\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u4e2d\uff0c\u64e6\u9664\u4e24\u4e2a\u5bf9\u89d2\u70b9\u540e\uff0c\u5269\u4f59\u4e24\u4e2a\u70b9\u4e4b\u95f4\u7684\u66fc\u54c8\u987f\u8ddd\u79bb\u4e3a $2$\u3002<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u89e3\u9898\u601d\u8def<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u9053\u9898\u6211\u5b66\u5230\u6700\u5927\u7684\u5730\u65b9\u5c31\u662f\uff1a\u5bf9\u4e8e\u4efb\u610f\u4e24\u70b9 $P_i(x_i, y_i)$ \u548c $P_j(x_j, y_j)$\uff0c\u53ef\u4ee5\u7528\u6052\u7b49\u5f0f\u8f6c\u5316\u4e3a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$<br>|x_i &#8211; x_j| + |y_i &#8211; y_j| = \\max\\left{ |(x_i + y_i) &#8211; (x_j + y_j)|,\\ |(x_i &#8211; y_i) &#8211; (x_j &#8211; y_j)| \\right}<br>$$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uff08\u53d6\u7edd\u5bf9\u503c\u540e\u53d6\u6700\u5927\uff0c\u5b9e\u9645\u7b49\u4ef7\u4e8e\u4e24\u4e2a\u7ef4\u5ea6\u5dee\u503c\u7684\u6700\u5927\u503c\uff09\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4ee4 $u_i = x_i + y_i$\uff0c$v_i = x_i &#8211; y_i$\uff0c\u90a3\u4e48\u4e00\u7ec4\u70b9\u7684\u6700\u5927\u66fc\u54c8\u987f\u8ddd\u79bb\u5c31\u662f<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$<br>D = \\max\\left( \\max_i u_i &#8211; \\min_i u_i,\\ \\max_i v_i &#8211; \\min_i v_i \\right)<br>$$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u56e0\u6b64\u5220\u9664\u70b9\u540e\u53ea\u9700\u8981\u91cd\u65b0\u8ba1\u7b97\u5269\u4f59\u70b9\u4e2d $u$ \u548c $v$ \u7684\u6781\u5dee\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u82e5\u5220\u9664 $k$ \u4e2a\u70b9\uff08$k \\le 2$\uff09\uff0c\u6211\u4eec\u53ea\u9700\u8981\u8ba1\u7b97\u5269\u4f59\u70b9\u4e0a\u4e0a\u8ff0\u4e24\u4e2a\u5dee\u503c\u7684\u6700\u5927\u503c\u3002\u4e3a\u4e86\u6700\u5c0f\u5316\u76f4\u5f84\uff0c\u6211\u4eec\u8981\u5c3d\u91cf\u5220\u9664\u6781\u7aef\u70b9\u2014\u2014\u5373\u8d21\u732e\u6700\u5927\u503c\u548c\u6700\u5c0f\u503c\u7684\u70b9\u3002<br>\u771f\u6b63\u53ef\u80fd\u5f71\u54cd\u6700\u7ec8\u7b54\u6848\u7684\u70b9\u6709\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>$x+y$ \u6700\u5927\u7684\u524d $2$ \u4e2a\u70b9<\/li>\n\n\n\n<li>$x+y$ \u6700\u5c0f\u7684\u524d $2$ \u4e2a\u70b9<\/li>\n\n\n\n<li>$x-y$ \u6700\u5927\u7684\u524d $2$ \u4e2a\u70b9<\/li>\n\n\n\n<li>$x-y$ \u6700\u5c0f\u7684\u524d $2$ \u4e2a\u70b9<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">\u5c06\u8fd9\u4e9b\u70b9\u53bb\u91cd\u540e\uff0c\u5019\u9009\u70b9\u4e0d\u8d85\u8fc7 $8$ \u4e2a\uff0c\u7136\u540e\u679a\u4e3e\u5220\u9664\u5176\u4e2d $2$ \u4e2a\u70b9\u7684\u76f4\u5f84\uff0c\u53d6\u6700\u5c0f\u503c\u5373\u53ef\u3002<br>\u5f53 $n \\le 3$ \u65f6\uff0c\u7b54\u6848\u5c31\u662f $0$\uff0c\u52a0\u4e2a\u7279\u5224\u3002<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u53c2\u8003\u4ee3\u7801<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/Sunshine sunshine ladybugs awake,\n\/\/Clap your hooves and do a little shack.\n#include&lt;bits\/stdc++.h&gt;\n\n#define int long long\n#define endl \"\\n\"\n\nusing namespace std;\n\nusing PII = pair&lt;int,int&gt;;\nconst int MAXN = 300005;\nconst int mod = 998244353;\nconst int INF = 0x3f3f3f3f3f3f3f3f;\n\nvoid solve(){\n    int n; cin &gt;&gt; n;\n    vector&lt;PII&gt; point(n);\n    vector&lt;PII&gt; sum, diff;\n\n    for(int i = 0; i &lt; n; i++){\n        auto &amp;&#91;x, y] = point&#91;i];\n        cin &gt;&gt; x &gt;&gt; y;\n        sum.push_back({x + y, i});\n        diff.push_back({x - y, i});\n    }\n\n    sort(sum.begin(), sum.end());\n    sort(diff.begin(), diff.end());\n\n    set&lt;int&gt; candidate;\n    int take = min(2ll, n);\n\n    for(int i = 0; i &lt; take; i++){\n        candidate.insert(sum&#91;i].second);\n        candidate.insert(sum&#91;n - 1 - i].second);\n        candidate.insert(diff&#91;i].second);\n        candidate.insert(diff&#91;n - 1 - i].second);\n    }\n\n    vector&lt;int&gt; candidates(candidate.begin(), candidate.end());\n\n    auto calculate = &#91;&amp;](int ban1, int ban2) -&gt; int {\n        int minU = INF, maxU = -INF;\n        int minV = INF, maxV = -INF;\n        int count = 0;\n\n        for(int i = 0; i &lt; n; i++){\n            if(i == ban1 || i == ban2) continue;\n            count++;\n            auto &#91;x, y] = point&#91;i];\n            int u = x + y;\n            int v = x - y;\n            minU = min(minU, u);\n            maxU = max(maxU, u);\n            minV = min(minV, v);\n            maxV = max(maxV, v);\n        }\n\n        if(count &lt; 2) return 0;\n        return max(maxU - minU, maxV - minV);\n    };\n\n    if (n &lt;= 3) {\n        cout &lt;&lt; 0 &lt;&lt; endl;\n        return;\n    }\n\n    int answer = INF;\n    int m = candidates.size();\n\n    for (int i = 0; i &lt; m; i++) {\n        for (int j = i + 1; j &lt; m; j++) {\n            answer = min(answer, calculate(candidates&#91;i], candidates&#91;j]));\n        }\n    }\n\n    cout &lt;&lt; answer &lt;&lt; endl;\n}\n\nsigned main() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    int t; cin &gt;&gt; t;\n    while(t--) solve();\n    return 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>K. \u70b9\u76f4\u5f84 \u9898\u76ee\u63cf\u8ff0 \u4f50\u7f57\u53c8\u5728\u67d0\u4e2a\u5e73\u5766\u7684\u5c0f\u5c9b\u4e0a\u8ff7\u8def\u4e86\uff0c\u5c9b\u4e0a\u6709 $n$ \u4e2a\u5730\u6807\u3002\u5c71\u6cbb\u6c14\u574f\u4e86\uff0c\u60f3\u7528\u5730\u56fe\u7ed9\u4ed6\u6307\u8def\u3002 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":130,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-249","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-learn"],"_links":{"self":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/249","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/comments?post=249"}],"version-history":[{"count":2,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/249\/revisions"}],"predecessor-version":[{"id":252,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/249\/revisions\/252"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/media\/130"}],"wp:attachment":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/media?parent=249"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/categories?post=249"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/tags?post=249"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}