Codeforces Round #707 (Div. 2) C(抽屉原理)

题意

给你一个数组,找出四个数,使得其中两个的和等于另外两个的和,输出下标。最多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;
}

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇