完美的数组——计蒜客T1432

一个数组被称为完美的,当且仅当其中存在一个元素,它的值是除了它之外剩下的所有元素的和。

蒜头君现在获得了一个数组。他想去掉数组中的一个元素,使得这个数组变成完美的。

他想知道这个数组有几种方案可以变成完美的。当去掉的元素在原数组中的位置不同时,即为不同的方案。

输入格式

输入的第一行包含一个整数(2<= n <=10^5)

输入的第二行包括 n 个整数,为蒜头君获得的数组里面的每个元素
ai。

输出格式

输出有两行。

第一行是方案的个数 k。第二行有 k 个用单个空格分开的整数,分别表示去掉的元素在原数组中的位置(按照输入的顺序)。

说明:如果没有方案,输出一个 0即可。

输出时每行末尾的多余空格,不影响答案正确性

样例输入1

5
2 5 1 2 2

样例输出1

3
1 4 5

样例输入2

4
8 3 5 2

样例输出2

2
1 4

样例输入3

5
2 1 2 4 3

样例输出3

0

题目分析:

本题中充当总和的数一定是剔除异元素之后数组中的最大值

但如果剔除的数字就是原本数组中的最大值,则充当判断的数将变成原本数组中的次大值(即小于等于原本最大值的值)

因此在判断时要分别判断剔除的值是否为最大值情况

由数学知识不难得出→由于剔除后 “其余的值之和” = “最大值”,因此“其余的值之和” + “最大值” = 2*“最大值”。

因此只需引入一个变量(本题我使用的是v)另其等于(sum-a[i])/2.0,即总和剔除一个数后再除以 2,判断v是否等于最大值即可,如若相等,sign++,并将位数记录到b数组中。

代码如下

#include<iostream>
using namespace std;
int main()</