题目描述

难度分:$1400$

输入$k(2 \leq k \leq 2 \times 10^5)$。

然后输入$k$行，每行输入$n(1 \leq n \lt 2 \times 10^5)$和长为$n$的数组，数组元素范围 $[-10^4,10^4]$。所有$n$之和$\leq 2 \times 10^5$。

从这$k$个数组中，选出两个数组$a$和$b$，然后从$a$、$b$中各删除恰好一个元素，要求删除后 $sum(a)=sum(b)$。空数组的元素和为$0$。

如果无法做到，输出NO，否则输出YES。

然后输出数组$a$是输入的第几个数组，以及$a$中删除的元素在$a$的下标（从$1$开始）。

然后输出数组$b$是输入的第几个数组，以及$b$中删除的元素在$b$的下标（从$1$开始）。

输入样例$1$

2
5
2 3 1 3 2
6
1 1 2 2 2 1

输出样例$1$

YES
2 6
1 2

输入样例$2$

3
1
5
5
1 1 1 1 1
2
2 3

输出样例$2$

NO

输入样例$3$

4
6
2 2 2 2 2 2
5
2 2 2 2 2
3
2 2 2
5
2 2 2 2 2

输出样例$3$

YES
2 2
4 1

算法

哈希表+枚举

其实只要预处理出一个映射就能够进行高效的枚举，预处理出一个映射“sum $\rightarrow i \rightarrow j$”$mp$，它表示将第$i$个数组的第$j$个元素删除后，第$i$个数组的累加和为$sum$。光凭这个含义，很容易在读入数据的时候就能预处理出这个映射表。

而只要有了这个映射表，在遍历$mp$的时候判断某个累加和$sum$是否存在两个位置的删除策略（在不同数组中删除元素都能得到相同的和）都能得到$sum$，随便选择两种输出即可。

复杂度分析

时间复杂度

读入数据的时候就可以预处理出这个哈希表$mp$，接下来再遍历一遍哈希表就可以得到答案。因此，算法的时间复杂度为$O(kn)$。

空间复杂度

除去输入的$k$个数组所占空间，主要是哈希表$mp$所消耗的空间。在最差情况下，每个数组的每个位置删除后都能得到不同的数组和，一共有$kn$个位置，那就能得到$kn$个不同的和。因此，算法的额外空间复杂度为$O(kn)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

int k, n, ai;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    cin >> k;
    unordered_map<int, unordered_map<int, int, custom_hash>, custom_hash> mp;
    for(int i = 0; i < k; i++) {
        vector<int> a;
        cin >> n;
        int tot = 0;
        for(int j = 0; j < n; j++) {
            cin >> ai;
            tot += ai;
            a.push_back(ai);
        }
        for(int j = 0; j < n; j++) {
            mp[tot - a[j]][i + 1] = j + 1;
        }
    }
    for(auto&[sum, a2pos]: mp) {
        if(a2pos.size() > 1) {
            puts("YES");
            int i1 = a2pos.begin()->first, j1 = a2pos.begin()->second;
            int i2 = next(a2pos.begin())->first, j2 = next(a2pos.begin())->second;
            printf("%d %d\n%d %d\n", i1, j1, i2, j2);
            exit(0);
        }
    }
    puts("NO");
    return 0;
}