【每日一题】CF988 C. Equal Sums | 排序 | 简单

本文主要是介绍【每日一题】CF988 C. Equal Sums | 排序 | 简单，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目内容

原题链接

给定 $k$ 个数组，第 $i$ 个数组的长度为 $n_i$ 。

问是否可以选择两个数组，编号分别为 $a$ 和 $b$ ，从 $a$ 和 $b$ 中各删除一个数，使得两者的数组和相同。

如果可以，输出三行

• 第一行输出 YES
• 第二行输出选择的数组 $a$ 的编号以及数组 $a$ 中删除的数组元素的下标（从 $1$ 开始）
• 第三行输出选择的数组 $b$ 的编号以及数组 $b$ 中删除的数组元素的下标（从 $1$ 开始）

如果不可以，输出一行 NO

数据范围

• $2\le k\le 2\cdot 10^5$
• $1\le n_i<2\cdot 10^5$
• $-10^4\le ai,j\le 10^4$ ，$a_{i,j}$ 为第 $i$ 个数组的第 $j$ 个元素
• $\sum _{i=1}^k{n}_i\le 2\cdot 10^5$

题解

考虑对于第 $i$ 个数组，其所有元素和为 $sum$ 。
将第 $i$ 个数组的第 $j$ 个元素删除后，存下 $(sum-a_{i,j},i,j)$ 三元组

对于所有数组的所有元素，共有 $\sum _{i=1}^k{n}_i$ 个元素

按照 $sum-a_{i,j}$ 排序这些三元组，然后判断第一关键字相同的三元组中，是否存在有 $i$ 不同的三元组，如果有则是存在答案，输出即可。

时间复杂度：$O(n\log n),n=\sum _{i=1}^k{n}_i$

代码

#include <bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int k;cin >> k;vector<pair<int, pair<int, int>>> vec;for (int i = 1; i <= k; ++i) {int n;cin >> n;int sum = 0;vector<int> a(n);for (int j = 0; j < n; ++j) {cin >> a[j];sum += a[j];}for (int j = 0; j < n; ++j) {vec.emplace_back(sum - a[j], make_pair(i, j + 1));}}sort(vec.begin(), vec.end());int n = vec.size();for (int i = 0; i < n; ++i) {int j = i + 1;while (j < n && vec[j].first == vec[i].first) j += 1;if (vec[i].second.first != vec[j - 1].second.first) {cout << "YES\n";cout << vec[i].second.first << " " << vec[i].second.second << "\n";cout << vec[j - 1].second.first << " " << vec[j - 1].second.second << "\n";return 0;}i = j - 1;}cout << "NO\n";return 0;
}

这篇关于【每日一题】CF988 C. Equal Sums | 排序 | 简单的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---