题目描述

难度分:$1300$

输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^6)$。

对于数组$b$，如果$b$中存在一个数$x$，使得$x=b$中其余元素之和，则称$b$为「好数组」。

如果删除$a[i]$可以使剩余元素组成好数组，则称$i$为「好下标」。

输出$a$的好下标的个数，以及所有好下标（任意顺序）。注意下标从$1$开始。

输入样例$1$

5
2 5 1 2 2

输出样例$1$

3
4 1 5

输入样例$2$

4
8 3 5 2

输出样例$2$

2
1 4 

输入样例$3$

5
2 1 2 4 3

输出样例$3$

0

算法

有序表

先求出整个数组的累加和$tot$，并将二元组$(a[i],i)$放入到一个有序集合中。然后遍历$i \in [1,n]$，假设此时要将$a[i]$删除，那么剩余数组的累加和就会变为$tot-a[i]$，将$(a[i],i)$从有序集合中删除，并从中选出元素值最大的那个二元组，获得此时剩余数组中的最大值$mx$。只要满足$tot-a[i]=2mx$，说明剩余数组中存在一个元素的值为$mx$，而剩余数组除去这个元素后其他元素的累加和也为$mx$，剩余数组是一个好数组，$i$是一个好下标。

然后继续考虑后面的$i$，但是需要恢复现场，将二元组$(a[i],i)$重新插回到有序集合中。

复杂度分析

时间复杂度

遍历$i \in [1,n]$的时间复杂度为$O(n)$，对于每个$i$，存在有序表的插入和删除操作，时间复杂度是$O(log_2n)$的。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

额外空间主要是有序集合，它的内部在整个算法过程中都存放着$O(n)$数量级别的二元组，因此算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, a[N];

int main() {
    scanf("%d", &n);
    set<pair<int, int>> st;
    long long tot = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        st.insert({a[i], i});
        tot += a[i];
    }
    vector<int> pos;
    for(int i = 1; i <= n; i++) {
        st.erase({a[i], i});
        int mx = st.rbegin()->first;
        if(tot - a[i] == 2*mx) {
            pos.push_back(i);
        }
        st.insert({a[i], i});
    }
    printf("%d\n", (int)pos.size());
    for(int x: pos) printf("%d ", x);
    return 0;
}