题意就是找删去一个元素后和相同的组和删除的元素
1.所以可以直接用$O(n)$的时间求出每个组的和
2.然后遍历一遍所有的组,对于组内的每个元素,用本组的和减去它,就可以得到删除它的和
3.此时就可以用哈希表记录它的值,因为是哈希表,所以前面组的插入的值能在$O(1)$的时间内找到,建立一个映射关系保存该组对应的一个id和删除元素的下标就好了
最后需要注意下哈希表下标可能为负数,补上和的上限就好了
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <unordered_map>
#define f1(i,a,b) for(int i = a; i <= b; i ++)
#define f2(i,a,b) for(int i = a; i >= b; i --)
using namespace std;
typedef long long LL;
const int N = 200010;
vector<int> all[N];
int sum[N];
int k;
struct Node{
int who, num;
}table[N];
void input()
{
cin >> k;
for(int i = 1; i <= k; i ++)
{
int a; scanf("%d", &a);
for(int j = 1, v; j <= a; j ++)
scanf("%d", &v), all[i].push_back(v), sum[i] += v;
}
}
void solve()
{
unordered_map<int, int> H;
int idx = 0;
for(int i = 1; i <= k; i ++)
{
for(int j = 0; j < all[i].size(); j ++)
{
int diff = sum[i] - all[i][j];
if(H.count(diff + 200010))
{
auto & t = table[H[diff + 200010]];
if(t.who == i) continue;
//cout << all[id].size() << endl;
puts("YES");
printf("%d %d\n", i, j+1);
printf("%d %d\n", t.who, t.num+1);
return ;
}
else H[diff + 200010] = idx, table[idx] = {i, j}, idx ++;
}
}
puts("NO");
}
int main()
{
input();
solve();
return 0;
}
为啥我的C++用不了unordered_map啊
版本问题吧,C98貌似没有,C11才有的