当前位置：网站首页>Codeforces Round ＃707 (Div. 2) C（抽屉原理）

Codeforces Round ＃707 (Div. 2) C（抽屉原理）

2022-08-08 19:01:00 【Here_SDUT】

题意

给你一个数组，找出四个数，使得其中两个的和等于另外两个的和，输出下标。最多2e5个数，每个数范围为1-2.5e6。

分析

由于数字范围为1-2.5e6，所以两个数字相加最多达到5e6，运用抽屉原理知道，如果有5e6+1个数，那么这些数里一定有数相同。所以我们可以直接暴力合并所有的数，最多合并5e6+1次就会产生至少两个相同的数，直接跳出循环。还有一个坑，本题不能顺序遍历，而是要按间隔遍历，样例8会卡顺序遍历。顺序遍历的缺点是冲突的风险太大了，每次便利的时候，对于内循环的所有结果都不能贡献给答案，因为有一个共同的数。

代码

//                              _ooOoo_
//                             o8888888o
//                             88" . "88
//                             (| -_- |)
//                              O\ = /O
//                           ____/`---'\____
//                        .   ' \| |// `.
//                         / \||| : |||// \
//                        / _||||| -:- |||||- \
//                         | | \\ - /// | |
//                       | \_| ''\---/'' | |
//                        \ .-\__ `-` ___/-. /
//                    ___`. .' /--.--\ `. . __
//                  ."" '< `.___\_<|>_/___.' >'"".
//                 | | : `- \`.;`\ _ /`;.`/ - ` : | |
//                    \ \ `-. \_ __\ /__ _/ .-` / /
//           ======`-.____`-.___\_____/___.-`____.-'======
//                              `=---='
//
//           .............................................
//                   佛祖保佑     一发AC     永无BUG
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 7e6 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
vector<PII> num[maxn];
inline int read() {
    int X = 0;
    bool flag = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') flag = 0;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        X = (X << 1) + (X << 3) + ch - '0';
        ch = getchar();
    }
    if (flag) return X;
    return ~(X - 1);
}
int a[maxn];
int main(int argc, char const *argv[]) {
    int n 9;
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j + i <= n; j++) {
            int x = a[j] + a[j + i];
            num[x].push_back({j, j + i});
            for (int k = 0; k < num[x].size(); k++) {
                if (num[x][k].first == j || num[x][k].first == j + i ||
                    num[x][k].second == j || num[x][k].second == j + i)
                    continue;
                puts("YES");
                cout << j << ' ' << j + i << ' ' << num[x][k].first << ' '
                     << num[x][k].second << endl;
                return 0;
            }
        }
    }
    // for (int i = 1; i <= n; i++) {
    //     for (int j = i + 1; j <= n; j++) {
    //         int x = a[i] + a[j];
    //         num[x].push_back({i, j});
    //         for (int k = 0; k < num[x].size(); k++) {
    //             if (num[x][k].first == i || num[x][k].first == j ||
    //                 num[x][k].second == i || num[x][k].second == j)
    //                 continue;
    //             puts("YES");
    //             cout << i << ' ' << j << ' ' << num[x][k].first << ' '
    //                  << num[x][k].second << endl;
    //             return 0;
    //         }
    //     }
    // }
    puts("NO");
    return 0;
}

原网站

版权声明
本文为[Here_SDUT]所创，转载请带上原文链接，感谢
https://cloud.tencent.com/developer/article/2068400