完美的数组——计蒜客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()
{
          
   
    int i,j,sign=0,n,a[200000],b[200000],sum=0,x,temp;
    //此处a、b用new和delete动态分配也可，但由于题目的范围限制直接写出更方便
    cin>>n;
    int max=0,Max=0;//max是最大值，Max是次大值
    for(i=0;i<n;i++)
    {
          
   
        cin>>a[i];
        sum+= a[i];
        if(a[i]>max) {
          
   max=a[i]; temp=i;}//找到最大值
    }
    for(i=0;i<n;i++)
    {
          
   
        if(a[i]>Max && temp!=i) Max=a[i];//找到次大值
    }
    double v;
    x=0;
    for(i=0;i<n;i++)
    {
          
   
        v=(double)(sum-a[i])/2.0;
        if(a[i]!=max && v==max)//去掉的不是最大值
        {
          
   
            sign++;//记录方案总数
            b[x++]=i+1;//b数组存储的是去掉的元素在原数组中的位置
        }
        if(a[i]==max && v==Max)//去掉的是最大值，此时v应该等于次大值
        {
          
   
            sign++;
            b[x++]=i+1;
        }
    }
    cout<<sign<<endl;
    for(i=0;i<x;i++) cout<<b[i]<< ;
    return 0;
}

如有错误或更好的算法欢迎各位大佬指正分享。