{"id":506,"date":"2025-08-14T15:55:11","date_gmt":"2025-08-14T07:55:11","guid":{"rendered":"https:\/\/www.george-blog.top\/?p=506"},"modified":"2025-08-20T20:05:25","modified_gmt":"2025-08-20T12:05:25","slug":"%e4%ba%8c%e5%88%86%e4%b8%93%e9%a2%98","status":"publish","type":"post","link":"https:\/\/www.george-blog.top\/?p=506","title":{"rendered":"\u4e8c\u5206\u4e13\u9898"},"content":{"rendered":"

\u6ce8\u610f\uff1a
\n        1\u3001\u4e13\u9898\u7cfb\u5217\u96be\u5ea6\u968f\u673a\u3002\u7531\u4e8e\u6709\u4e9bOJ\u7f51\u7ad9\u4e0d\u6613\u88ab\u6253\u5f00\uff0c\u65e0\u6cd5\u67e5\u770b\u539f\u9898\u76ee\uff0c\u6240\u4ee5\u6240\u6709\u7684\u9898\u76ee\u94fe\u63a5\u90fd\u6307\u5411VJ\uff08Virtual Judge<\/a>\uff09\u4e2d\u5bf9\u5e94\u7684\u9898\u76ee\u3002VJ\u4e2d\u6709\u9898\u76ee\u7684\u539f\u51fa\u5904\uff0c\u9700\u8981\u7684\u81ea\u53d6\uff01
\n        2\u3001\u4e3a\u4e86\u8ba9\u5927\u5bb6\u66f4\u6613\u4e8e\u7406\u89e3AC\u7801\uff0c\u6bcf\u4e00\u9053\u9898\u7684\u4ee3\u7801\u98ce\u683c\u90fd\u7528AI\u8fdb\u884c\u4e86\u4f18\u5316\u3002<\/font><\/strong><\/p>\n

\n

A\u3001\u8df3\u77f3\u5934\uff08\u6d1b\u8c37 P2678\uff09<\/h1>\n

\u9898\u76ee\u94fe\u63a5\uff1a\u8df3\u77f3\u5934\uff08\u6d1b\u8c37 P2678\uff09<\/a><\/strong><\/p>\n

\u6807\u7b7e\uff1a\u4e8c\u5206<\/code><\/p>\n

AC\u7801\uff1a<\/strong><\/p>\n

#include <bits\/stdc++.h>\nusing namespace std;\n#define endl "\\n" \n\nint L, N, M;\nint rock[50050];\n\nbool check(int distance) {\n    int removed = 0;\n    int prerock = 0;\n    for (int i = 0; i < N; ++i) {\n        if (rock[i] - prerock < distance) {\n            removed++;\n        } else {\n            prerock = rock[i];\n        }\n    }\n    if (L - prerock < distance) {\n        removed++;\n    }\n    return removed <= M;\n}\n\nint bsearch() {\n    int  l = -1, r = L;\n    while (l + 1 != r) {\n        int mid = (l + r) \/ 2;\n        if (check(mid)) {\n            l = mid;\n        } else {\n            r = mid;\n        }\n    }\n    return l;\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n\n    cin >> L >> N >> M;\n    for (int i = 0; i < N; ++i) {\n        cin >> rock[i];\n    }\n    if (N == 0 && M == 0) {\n        cout << L << endl;\n    } else {\n        cout << bsearch() << endl;\n    }\n    return 0;\n}    <\/code><\/pre>\n
B\u3001\u6728\u6750\u52a0\u5de5\uff08\u6d1b\u8c37 P2440\uff09<\/h1>\n
\u9898\u76ee\u94fe\u63a5\uff1a\u6728\u6750\u52a0\u5de5\uff08\u6d1b\u8c37 P2440\uff09<\/a><\/strong><\/p>\n
\u6807\u7b7e\uff1a\u4e8c\u5206<\/code><\/p>\n
AC\u7801\uff1a<\/strong><\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\n#define endl "\\n"\n\nint n, k;\nint logs[100050];\nint maxx = 0;\n\nbool check(int mid) {\n    if (mid == 0) {\n        return true;\n    }\n    int cnt = 0;\n    for (int i = 0; i < n; ++i) {\n        cnt += logs[i] \/ mid;\n    }\n    return cnt >= k;\n}\n\nint bsearch() {\n    int l = -1, r = maxx;\n    while (l + 1 != r) {\n        int mid = (l + r) \/ 2;\n        if (check(mid)) {\n            l = mid;\n        } else {\n            r = mid;\n        }\n    }\n    return l;\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n\n    cin >> n >> k;\n    for (int i = 0; i < n; ++i) {\n        cin >> logs[i];\n        maxx = max(maxx, logs[i]);\n    }\n    cout << bsearch() << endl;\n    return 0;\n}    <\/code><\/pre>\n
C\u3001Set or Decrease\uff08CodeForces 1622C\uff09<\/h1>\n
\u9898\u76ee\u94fe\u63a5\uff1aSet or Decrease\uff08CodeForces 1622C\uff09<\/a><\/strong><\/p>\n
\u6807\u7b7e\uff1a\u4e8c\u5206<\/code><\/p>\n
AC\u7801\uff1a<\/strong><\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\n#define endl "\\n"\n#define int long long\n\nint a[200050], presum[200050];\nint n, k;\n\nbool cmp(int x, int y) {\n    return x > y;\n}\n\nbool check(int mid) {\n    for (int i = 0; i <= min(mid, n - 1); i++) {\n        int mi = a[n] - (mid - i);\n        int sum_ = presum[n - 1] - presum[i] + (i + 1) * mi;\n        if (sum_ <= k) {\n            return true;\n        }\n    }\n    return false;\n}\n\nint bsearch(int sum, int k) {\n    int l = -1, r = sum - k;\n\n    while (l + 1 != r) {\n        int mid = (l + r) \/ 2;\n\n        if (check(mid)) {\n            r = mid;\n        } else {\n            l = mid;\n        }\n    }\n\n    return r;\n}\n\nsigned main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n\n    int t;\n    cin >> t;\n\n    while (t--) {\n        cin >> n >> k;\n        int sum = 0;\n\n        for (int i = 1; i <= n; i++) {\n            cin >> a[i];\n            sum += a[i];\n        }\n\n        sort(a + 1, a + 1 + n, cmp);\n\n        for (int i = 1; i <= n; i++) {\n            presum[i] = presum[i - 1] + a[i];\n        }\n\n        if (sum <= k) {\n            cout << 0 << endl;\n        } else {\n            int ans = bsearch(sum, k);\n            cout << ans << endl;\n        }\n    }\n\n    return 0;\n}<\/code><\/pre>\n
D\u3001Ice Cream Balls\uff08CodeForces 1862D\uff09<\/h1>\n
\u9898\u76ee\u94fe\u63a5\uff1aIce Cream Balls\uff08CodeForces 1862D\uff09<\/a><\/strong><\/p>\n
\u6807\u7b7e\uff1a\u4e8c\u5206<\/code><\/p>\n
AC\u7801\uff1a<\/strong><\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\n#define endl "\\n"\n\nlong long n;\n\nbool check(long long x) {\n    long long temp = x * (x - 1) \/ 2;\n    return temp <= n;\n}\n\nlong long bsearch() {\n    long long l = -1, r = 2e9;\n    while (l + 1 != r) {\n        long long mid = (l + r) \/ 2;\n        if (check(mid)) {\n            l = mid;\n        } else {\n            r = mid;\n        }\n    }\n    return l;\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n\n    int t;\n    cin >> t;\n    while (t--) {\n        cin >> n;\n        if (n == 1) {\n            cout << 2 << endl;\n            continue;\n        }\n        long long result = bsearch();\n        cout << result + (n - (result * (result - 1) \/ 2)) << endl;\n    }\n    return 0;\n}<\/code><\/pre>\n
E\u3001Vika and the Bridge\uff08CodeForces 1848B\uff09<\/h1>\n
\u9898\u76ee\u94fe\u63a5\uff1aVika and the Bridge\uff08CodeForces 1848B\uff09<\/a><\/strong><\/p>\n
\u6807\u7b7e\uff1a\u4e8c\u5206<\/code><\/p>\n
AC\u7801\uff1a<\/strong><\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\n#define endl "\\n"\n\nbool check(int mid, const vector<int>& pos, int n) {\n    int m = pos.size();\n    int last = -1;\n    int repaint = 0;\n\n    for (int i = 0; i < m; ++i) {\n        int gap = pos[i] - last - 1;\n        if (gap > mid) {\n            repaint++;\n            if (repaint > 1) {\n                return false;\n            }\n            if (gap \/ 2 > mid) {\n                return false;\n            }\n        }\n        last = pos[i];\n    }\n\n    int gap = n - pos.back() - 1;\n    if (gap > mid) {\n        repaint++;\n        if (repaint > 1) {\n            return false;\n        }\n        if (gap \/ 2 > mid) {\n            return false;\n        }\n    }\n\n    return true;\n}\n\nint bsearch(const vector<int>& pos, int n) {\n    int l = -1, r = n;\n\n    while (l + 1 != r) {\n        int mid = (l + r) \/ 2;\n\n        if (check(mid, pos, n)) {\n            r = mid;\n        } else {\n            l = mid;\n        }\n    }\n\n    return r;\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n\n    int t;\n    cin >> t;\n\n    while (t--) {\n        int n, k;\n        cin >> n >> k;\n\n        vector<int> c(n);\n        for (int i = 0; i < n; ++i) {\n            cin >> c[i];\n        }\n\n        vector<vector<int>> pos(k + 1);\n        for (int i = 0; i < n; ++i) {\n            pos[c[i]].push_back(i);\n        }\n\n        int ans = n;\n\n        for (int color = 1; color <= k; ++color) {\n            if (pos[color].empty()) {\n                continue;\n            }\n\n            int min_max_step = bsearch(pos[color], n);\n            ans = min(ans, min_max_step);\n        }\n\n        cout << ans << endl;\n    }\n\n    return 0;\n}<\/code><\/pre>\n
F\u3001Interview\uff08CodeForces 1807E\uff09<\/h1>\n
\u9898\u76ee\u94fe\u63a5\uff1aInterview\uff08CodeForces 1807E\uff09<\/a><\/strong><\/p>\n
\u6807\u7b7e\uff1a\u4e8c\u5206<\/code><\/p>\n
AC\u7801\uff1a<\/strong><\/p>\n
#include <iostream>\nusing namespace std;\n#define endl "\\n"\n\nconst int MAXN = 100005;\nint cows[MAXN];\nint n, f;\n\nbool check(double mid) {\n    double presum[MAXN] = {};\n    double min_sum = 0;\n\n    for (int i = 1; i <= n; ++i) {\n        presum[i] = presum[i - 1] + cows[i - 1] - mid;\n    }\n\n    for (int i = f; i <= n; ++i) {\n        min_sum = min(min_sum, presum[i - f]);\n        if (presum[i] - min_sum >= 0) {\n            return true;\n        }\n    }\n\n    return false;\n}\n\ndouble bsearch() {\n    double l = 0, r = 2000;\n\n    while (r - l > 1e-5) {\n        double mid = (l + r) \/ 2.0;\n        if (check(mid)) {\n            l = mid;\n        } else {\n            r = mid;\n        }\n    }\n\n    return r;\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n\n    cin >> n >> f;\n    for (int i = 0; i < n; ++i) {\n        cin >> cows[i];\n    }\n\n    double result = bsearch();\n    cout << int(result * 1000) << endl;\n\n    return 0;\n}<\/code><\/pre>\n
G\u3001Chat Ban\uff08CodeForces 1612C\uff09<\/h1>\n
\u9898\u76ee\u94fe\u63a5\uff1aCodeForces 1612C<\/a><\/strong><\/p>\n
\u6807\u7b7e\uff1a\u4e8c\u5206<\/code><\/p>\n
AC\u7801\uff1a<\/strong><\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\n#define endl "\\n"\n\nlong long k, x;\n\nbool check(long long mid) {\n    if (mid <= k) {\n        return (1 + mid) * mid \/ 2 >= x;\n    }\n    return (1 + k) * k \/ 2 + (k - 1 + 2 * k - mid) * (mid - k) \/ 2 >= x;\n}\n\nlong long bsearch() {\n    long long n = 2 * k - 1;\n    long long l = -1, r = n;\n    while (l + 1 != r) {\n        long long mid = (l + r) \/ 2;\n        if (check(mid)) {\n            r = mid;\n        } else {\n            l = mid;\n        }\n    }\n    return r;\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n    int t;\n    cin >> t;\n    while (t--) {\n        cin >> k >> x;\n        long long result = bsearch();\n        cout << result << endl;\n    }\n    return 0;\n}<\/code><\/pre>\n
H\u3001Pursuit\uff08CodeForces 1530C\uff09<\/h1>\n
\u9898\u76ee\u94fe\u63a5\uff1aPursuit\uff08CodeForces 1530C\uff09<\/a><\/strong><\/p>\n
\u6807\u7b7e\uff1a\u4e8c\u5206<\/code><\/p>\n
AC\u7801\uff1a<\/strong><\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\n#define endl "\\n"\n\nint n;\nvector<int> a, b;\n\nbool cmp(int x, int y) {\n    return x > y;\n}\n\nbool check(int mid) {\n    int num = (n + mid) - (n + mid) \/ 4;\n    int suma = 0, sumb = 0;\n    vector<int> backupa = a;\n    vector<int> backupb = b;\n\n    for (int i = 0; i < mid; ++i) {\n        backupa.push_back(100);\n        backupb.push_back(0);\n    }\n\n    sort(backupa.begin(), backupa.end(), cmp);\n    sort(backupb.begin(), backupb.end(), cmp);\n\n    for (int i = 0; i < num; ++i) {\n        suma += backupa[i];\n        sumb += backupb[i];\n    }\n\n    return suma < sumb;\n}\n\nint bsearch() {\n    int l = -1, r = 2 * n + 1;\n    while (l + 1 != r) {\n        int mid = (l + r) \/ 2;\n        if (check(mid)) {\n            l = mid;\n        } else {\n            r = mid;\n        }\n    }\n    return r;\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n\n    int t;\n    cin >> t;\n    while (t--) {\n        a.clear();\n        b.clear();\n        cin >> n;\n\n        int score;\n        for (int i = 0; i < n; ++i) {\n            cin >> score;\n            a.push_back(score);\n        }\n\n        for (int i = 0; i < n; ++i) {\n            cin >> score;\n            b.push_back(score);\n        }\n\n        sort(a.begin(), a.end(), cmp);\n        sort(b.begin(), b.end(), cmp);\n\n        int sum1 = 0, sum2 = 0;\n        for (int i = 0; i < n - n \/ 4; ++i) {\n            sum1 += a[i];\n            sum2 += b[i];\n        }\n\n        if (sum1 > sum2) {\n            cout << 0 << endl;\n        } else {\n            cout << bsearch() << endl;\n        }\n    }\n    return 0;\n}<\/code><\/pre>\n
I\u3001Best Cow Fences\uff08POJ 2018\uff09<\/h1>\n
\u9898\u76ee\u94fe\u63a5\uff1aBest Cow Fences\uff08POJ 2018\uff09<\/a><\/strong><\/p>\n
\u6807\u7b7e\uff1a\u6d6e\u70b9\u4e8c\u5206<\/code><\/p>\n
AC\u7801\uff1a<\/strong><\/p>\n
#include <iostream>\nusing namespace std;\n#define endl "\\n"\n\nconst int MAXN = 100005;\nint cows[MAXN];\nint n, f;\n\nbool check(double mid) {\n    double presum[MAXN] = {};\n    double min_sum = 0;\n\n    for (int i = 1; i <= n; ++i) {\n        presum[i] = presum[i - 1] + cows[i - 1] - mid;\n    }\n\n    for (int i = f; i <= n; ++i) {\n        min_sum = min(min_sum, presum[i - f]);\n        if (presum[i] - min_sum >= 0) {\n            return true;\n        }\n    }\n\n    return false;\n}\n\ndouble bsearch() {\n    double l = 0, r = 2000;\n\n    while (r - l > 1e-5) {\n        double mid = (l + r) \/ 2.0;\n        if (check(mid)) {\n            l = mid;\n        } else {\n            r = mid;\n        }\n    }\n\n    return r;\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n\n    cin >> n >> f;\n    for (int i = 0; i < n; ++i) {\n        cin >> cows[i];\n    }\n\n    double ans = bsearch();\n    cout << int(ans * 1000) << endl;\n\n    return 0;\n}<\/code><\/pre>\n
J\u3001\u5e73\u5747\u6570\uff08\u6d1b\u8c37 P1404\uff09<\/h1>\n
\u9898\u76ee\u94fe\u63a5\uff1a\u5e73\u5747\u6570\uff08\u6d1b\u8c37 P1404\uff09<\/a><\/strong><\/p>\n
\u6807\u7b7e\uff1a\u6d6e\u70b9\u4e8c\u5206<\/code><\/p>\n
AC\u7801\uff1a<\/strong><\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\n#define endl "\\n"\n\ndouble a[1000050], sum[1000050];\nint n, m;\n\nbool check(double mid) {\n    for (int i = 1; i <= n; i++) {\n        sum[i] = sum[i - 1] + (a[i] - mid);\n    }\n\n    double mi = 1e16;\n    for (int i = m; i <= n; i++) {\n        mi = min(mi, sum[i - m]);\n        if (sum[i] - mi >= 0) {\n            return true;\n        }\n    }\n    return false;\n}\n\nint bsearch() {\n    double l = 0, r = 1e9;\n    while (r - l > 1e-7) {\n        double mid = (l + r) \/ 2.0;\n        if (check(mid)) {\n            l = mid;\n        } else {\n            r = mid;\n        }\n    }\n    return r * 1000;\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n\n    cin >> n >> m;\n    for (int i = 1; i <= n; i++) {\n        cin >> a[i];\n    }\n\n    cout << bsearch() << endl;\n\n    return 0;\n}<\/code><\/pre>\n
K\u3001<\/h1>\n
\u9898\u76ee\u94fe\u63a5\uff1a<\/strong><\/p>\n
\u6807\u7b7e\uff1a\u4e8c\u5206+DFS\/BFS<\/code>\uff0c\u9009\u6700\u5408\u9002\u7684\u4e00\u79cd<\/p>\n
AC\u7801\uff1a<\/strong><\/p>\n
<\/code><\/pre>\n
L\u3001Drying\uff08POJ 3104\uff09<\/h1>\n
\u9898\u76ee\u94fe\u63a5\uff1aDrying\uff08POJ 3104\uff09<\/a><\/strong><\/p>\n
\u6807\u7b7e\uff1a\u4e8c\u5206<\/code><\/p>\n
AC\u7801\uff1a<\/strong><\/p>\n
#include <iostream>\n#include <algorithm>\nusing namespace std;\n#define endl "\\n"\n\nint n, k;\nint a[100010];\n\nbool check(int mid) {\n    int sum = 0;\n    for (int i = 0; i < n; ++i) {\n        if (a[i] > mid) {\n            sum += (a[i] - mid + k - 2) \/ (k - 1);\n        }\n        if (sum > mid) {\n            return false;\n        }\n    }\n    return true;\n}\n\nint bsearch() {\n    int l = -1, r = a[n - 1];\n    while (l + 1 != r) {\n        int mid = (l + r) \/ 2;\n        if (check(mid)) {\n            r = mid;\n        } else {\n            l = mid;\n        }\n    }\n    return r;\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n\n    while (cin >> n) {\n        for (int i = 0; i < n; ++i) {\n            cin >> a[i];\n        }\n        cin >> k;\n\n        sort(a, a + n);\n\n        if (k == 1) {\n            cout << a[n - 1] << endl;\n            continue;\n        }\n\n        int ans = bsearch();\n        cout << ans << endl;\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u6ce8\u610f\uff1a         1\u3001\u4e13 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[10,9],"class_list":["post-506","post","type-post","status-publish","format-standard","hentry","category-acm","tag-c","tag-9"],"_links":{"self":[{"href":"https:\/\/www.george-blog.top\/index.php?rest_route=\/wp\/v2\/posts\/506","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.george-blog.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.george-blog.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.george-blog.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.george-blog.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=506"}],"version-history":[{"count":1,"href":"https:\/\/www.george-blog.top\/index.php?rest_route=\/wp\/v2\/posts\/506\/revisions"}],"predecessor-version":[{"id":621,"href":"https:\/\/www.george-blog.top\/index.php?rest_route=\/wp\/v2\/posts\/506\/revisions\/621"}],"wp:attachment":[{"href":"https:\/\/www.george-blog.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=506"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.george-blog.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=506"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.george-blog.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=506"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}