题目描述

给定 k 个整数序列，其中第 i 个序列的长度为 li。

现在，请你进行以下操作：

从 k 个序列中，选出两个序列 i,j(i≠j)。
删掉序列 i 中的一个元素。
删掉序列 j 中的一个元素。
要求：操作完成后，序列 i 中的各元素之和等于序列 j 中的各元素之和。

输出合理操作方案。

我们规定，空序列的各元素之和为 0。

输入格式
第一行包含整数 k，表示共有 k 个序列。

每个序列的输入占两行。

第一行包含整数 li，表示序列长度。

第二行包含 li 个整数 a1,a2,…,ali，表示序列中各元素的值。

输出格式
如果不存在合理方案，则输出一行 NO。

否则首先输出一行 YES。

随后，第二行输出整数 i 和 x，第三行输出整数 j 和 y，表示选择序列 i 和 j，删除序列 i 中的第 x 个元素以及序列 j 中的第 y 个元素。

序列和元素下标都从 1 开始。

输出任意合理方案即可。

数据范围
前三个测试点满足 2≤k≤5，1≤li≤10。
全部测试点满足 2≤k≤2×105，1≤li<2×105，−104≤ai≤104。
同一测试点内所有 li 之和不超过 2×105。

样例

输入样例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

算法1

(字典) $O(n)$

1.字典记录好子和对应的行号和index即可

时间复杂度

参考文献

Python3 代码

k = int(input())

sub_sum__li_idx = dict()
find = False

for lj in range(k):
    if find == True:
        break
    an = int(input())    #当前的长度
    a = [int(x) for x in input().split()]
    tot_sum = sum(a)
    for j, y in enumerate(a):
        sub_sum = tot_sum - y
        if sub_sum in sub_sum__li_idx and sub_sum__li_idx[sub_sum][0] != lj + 1:
            res_li, res_x = sub_sum__li_idx[sub_sum]
            res_lj = lj + 1
            res_y = j + 1
            print('YES')
            print("{} {}".format(res_li, res_x))
            print("{} {}".format(res_lj, res_y))
            find = True
            break
        else:
            sub_sum__li_idx[sub_sum] = (lj + 1, j + 1)

if find == False:
    print("NO")

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int k;    cin >> k;
    map<long long, pair<int, int>> sub_sum__li_idx;
    bool find = false;

    for (int lj = 0; lj < k; lj ++)
    {
        if (find == true)
            break;

        int an;    cin >> an;
        vector<long long> a(an);
        for (int i = 0; i < an; i ++)
            cin >> a[i];

        long long tot_sum = accumulate(a.begin(), a.end(), 0LL);
        for (int j = 0; j < an; j ++)
        {
            long long y = a[j];
            long long sub_sum = tot_sum - y;
            if (sub_sum__li_idx.find(sub_sum) != sub_sum__li_idx.end())
            {
                if (sub_sum__li_idx[sub_sum].first != lj + 1)
                {
                    auto [res_li, res_x] = sub_sum__li_idx[sub_sum];
                    int res_lj = lj + 1;
                    int res_y = j + 1;
                    cout << "YES" << endl;
                    cout << res_li << ' ' << res_x << endl;
                    cout << res_lj << ' ' << res_y << endl;
                    find = true;
                    break;
                }
            }
            else
            {
                sub_sum__li_idx[sub_sum] = pair<int, int>{lj + 1, j + 1};
            }
        }
    }

    if (find == false)
        cout << "NO" << endl;

    return 0;
}

java 代码

import java.util.* ;
public class Main
{
    public static void main(String [] args)
    {
        Scanner scan = new Scanner(System.in);
        int k = scan.nextInt();

        Map<Long, int []> sub_sum__li_idx = new HashMap<>();
        boolean find = false;

        for (int lj = 0; lj < k; lj ++)
        {
            if (find == true)
                break;
            int an = scan.nextInt();
            long [] a = new long [an];
            for (int i = 0; i < an ; i ++)
                a[i] = scan.nextLong();

            long tot_sum = 0;
            for (long x : a)
                tot_sum += x;

            for (int j = 0; j < an; j ++)
            {
                long y = a[j];
                long sub_sum = tot_sum - y;
                if (sub_sum__li_idx.containsKey(sub_sum) != false)
                {
                    int [] li_idx = sub_sum__li_idx.get(sub_sum);
                    if (li_idx[0] != lj + 1)
                    {
                        int res_li = li_idx[0];
                        int res_x = li_idx[1];
                        int res_lj = lj + 1;
                        int res_y = j + 1;
                        System.out.println("YES");
                        System.out.println(res_li + " " + res_x);
                        System.out.println(res_lj + " " + res_y);
                        find = true;
                        break;
                    }
                }
                else
                {
                    int [] li_idx = {lj + 1, j + 1};
                    sub_sum__li_idx.put(sub_sum, li_idx);
                }
            }
        }

        if (find == false)
            System.out.println("NO");

    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla