{"id":310,"date":"2019-10-04T15:10:54","date_gmt":"2019-10-04T07:10:54","guid":{"rendered":"http:\/\/www.guanhaobo.cn\/?p=310"},"modified":"2019-10-04T15:10:54","modified_gmt":"2019-10-04T07:10:54","slug":"%e6%8c%91%e6%88%98%e7%a8%8b%e5%ba%8f%e8%ae%be%e8%ae%a1%e7%ab%9e%e8%b5%9b%ef%bc%88%e7%ac%ac2%e7%89%88%ef%bc%891-6-1-%e5%85%88%e4%bb%8e%e7%ae%80%e5%8d%95%e9%a2%98%e5%bc%80%e5%a7%8b-%e4%b8%89","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=310","title":{"rendered":"\u6311\u6218\u7a0b\u5e8f\u8bbe\u8ba1\u7ade\u8d5b\uff08\u7b2c2\u7248\uff091.6.1 \u5148\u4ece\u7b80\u5355\u9898\u5f00\u59cb \u2014 \u4e09\u89d2\u5f62"},"content":{"rendered":"

\u9898\u76ee<\/h3>\n

\u6709n\u6839\u68cd\u5b50\uff0c\u68cd\u5b50i\u7684\u957f\u5ea6\u4e3aai\u3002\u60f3\u8981\u4ece\u4e2d\u9009\u51fa3\u6839\u68cd\u5b50\u7ec4\u6210\u5468\u957f\u5c3d\u53ef\u80fd\u957f\u7684\u4e09\u89d2\u5f62\u3002\u8bf7\u8f93\u51fa\u6700\u5927\u7684\u5468\u957f\uff0c\u82e5\u65e0\u6cd5\u7ec4\u6210\u4e09\u89d2\u5f62\u5219\u8f93\u51fa0\u3002<\/p>\n

\u9650\u5236\u6761\u4ef6<\/h3>\n

3 \u2264 n \u2264 100
\n1 \u2264 ai \u2264 10^6<\/p>\n

\u8f93\u5165<\/h3>\n

n = 5
\na = {2, 3, 4, 5, 10}<\/p>\n

\u8f93\u51fa<\/h3>\n

12\uff08\u9009\u62e93\u30014\u30015\u65f6\uff09<\/p>\n

\u8f93\u5165<\/h3>\n

n = 4
\na = {4, 5, 10, 20}<\/p>\n

\u8f93\u51fa<\/h3>\n

0\uff08\u65e0\u8bba\u600e\u4e48\u9009\u90fd\u65e0\u6cd5\u7ec4\u6210\u4e09\u89d2\u5f62\uff09<\/p>\n

\u9898\u76ee\u5206\u6790<\/h3>\n

\u9009\u62e93\u6839\u68cd\u5b50\uff0c\u5b83\u4eec\u80fd\u7ec4\u6210\u4e09\u89d2\u5f62\u7684\u5145\u8981\u6761\u4ef6\u4e3a\u6700\u957f\u68cd\u5b50\u7684\u957f\u5ea6 < \u5176\u4f59\u4e24\u6839\u68cd\u5b50\u7684\u957f\u5ea6\u4e4b\u548c<\/code>\u3002
\n\u8fd9\u91cc\u7a0d\u5fae\u89e3\u91ca\u4e00\u4e0b\uff0c\u4efb\u610f\u4e24\u8fb9\u4e4b\u548c\u5927\u4e8e\u7b2c\u4e09\u8fb9\u3001\u4efb\u610f\u4e24\u8fb9\u4e4b\u5dee\u5c0f\u4e8e\u7b2c\u4e09\u8fb9\u3001\u6700\u957f\u7684\u8fb9\u5c0f\u4e8e\u5176\u4f59\u4e24\u8fb9\u4e4b\u548c\uff0c\u8fd9\u4e09\u53e5\u8bdd\u662f\u7b49\u4ef7\u7684\uff0c\u53ea\u8981\u6ee1\u8db3\u4efb\u610f\u4e00\u4e2a\u5c31\u90fdok\u4e86\u3002
\n\u4e66\u4e2d\u7ed9\u51fa\u4e86\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(n^3)\u7684\u7b97\u6cd5\uff0c\u4e09\u91cd\u5faa\u73af\uff0c\u904d\u5386\u6bcf\u4e00\u79cd\u60c5\u51b5\uff0c\u627e\u5230\u6700\u5927\u7684\u5468\u957f\u3002
\n\u4e66\u4e2d\u8bf4\u8fd8\u6709\u590d\u6742\u5ea6\u4e3aO(nlogn)\u7684\u7b97\u6cd5\uff0c\u7559\u7ed9\u8bfb\u8005\u601d\u8003\u3002<\/p>\n

O(nlogn)\u7684\u7b97\u6cd5<\/h3>\n

\u56e0\u4e3a\u6211\u4eec\u5bfb\u627e\u7684\u662f\u6700\u5927\u5468\u957f\uff0c\u6240\u4ee5\u53ef\u4ee5\u5148\u5c06n\u6761\u8fb9a1\u5230an\u4ece\u5c0f\u5230\u5927\u6392\u5e8f\uff0c\u9009\u62e9\u6700\u5927\u7684\u90a3\u4e00\u6761\u8fb9an\u5f53\u4f5c\u4e09\u89d2\u5f62\u4e2d\u6700\u957f\u7684\u8fb9\uff0c\u7136\u540e\u5224\u65ada(n-2)+a(n-1)<\/code>\u662f\u5426\u5927\u4e8ean\uff0c\u5982\u679c\u6210\u7acb\u90a3\u4e48a(n-2)+a(n-1)+an<\/code>\u5c31\u662f\u7b54\u6848\u3002\u5982\u679c\u4e0d\u6210\u7acb\uff0c\u90a3\u4e48\u9009\u62e9a(n-1)\u5f53\u4f5c\u4e09\u89d2\u5f62\u4e2d\u6700\u957f\u7684\u8fb9\uff0c\u7136\u540e\u5224\u65ada(n-3)+a(n-2)<\/code>\u662f\u5426\u5927\u4e8ea(n-1)\uff0c\u540c\u4e0a\uff0c\u4ee5\u6b64\u7c7b\u63a8\u3002
\n\u8fd9\u6837\uff0c\u6392\u5e8f\u7684\u590d\u6742\u5ea6\u662f O(nlogn)\uff0c\u5bfb\u627e\u7b54\u6848\u7684\u590d\u6742\u5ea6\u662fO(n)\uff0c\u6240\u4ee5\u8fd9\u4e2a\u7b97\u6cd5\u7684\u590d\u6742\u5ea6\u662fO(nlogn)<\/p>\n

\u4ee3\u7801<\/h3>\n

\u4e0a\u9762\u5206\u6790\u4e2d\u7684\u8fb9\u662fa1\u5230an\uff0c\u4ee3\u7801\u4e2d\u7684\u8fb9\u662fa[0]\u5230a[n-1]<\/p>\n

#include <bits\/stdc++.h>\nusing namespace std;\n\nint main()\n{\n    int i, n, a[105], ans = 0;\n    cin >> n;\n    for (i = 0; i < n; i++)\n        cin >> a[i];\n    sort(a, a + n);\n    for (i = n - 1; i >= 2; i--)\n    {\n        if (a[i] < a[i - 1] + a[i - 2])\n        {\n            ans = a[i] + a[i - 1] + a[i - 2];\n            break;\n        }\n    }\n    cout << ans << endl;\n    return 0;\n}\n<\/code><\/pre>\n
\u8fd0\u884c\u6d4b\u8bd5<\/h3>\n
\u5982\u679c\u4ee3\u7801\u5199\u7684\u4e0d\u5bf9\uff0c\u6b22\u8fce\u5927\u5bb6\u6279\u8bc4\u6307\u6b63\uff01
\n\"\"<\/p>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee \u6709n\u6839\u68cd\u5b50\uff0c\u68cd\u5b50i\u7684\u957f\u5ea6\u4e3aai\u3002\u60f3\u8981\u4ece\u4e2d\u9009\u51fa3\u6839\u68cd\u5b50\u7ec4\u6210\u5468\u957f\u5c3d\u53ef\u80fd\u957f\u7684\u4e09\u89d2\u5f62\u3002\u8bf7\u8f93\u51fa\u6700\u5927\u7684\u5468\u957f\uff0c\u82e5\u65e0\u6cd5\u7ec4 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[50,51],"class_list":["post-310","post","type-post","status-publish","format-standard","hentry","category-algo","tag-50","tag-51"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/310","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=310"}],"version-history":[{"count":0,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/310\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=310"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=310"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=310"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}