【思维题】 Good Array

思维题: 题目链接
大意:

  删除一个数,使得除了最大值之外剩下的数字之和等于最大值

思路:

1.先排下序,降序.

2.进行特判,如果删掉的值为最大值,则除了最大值(index=1)和次大值(index=2)之外的数字之和应该等于次大值。

3.一般情况,此时最大值一定为(index=1).

for(i=2->n)
  if(所有数的和-最大值-当前要删除的数的值==最大值)
     当前数的下标加入到答案集中

完整实现代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
  int index;
  int value;
}temp;
bool cmp(node a,node b){return a.value>b.value;}
vector<node> arr;
vector<int> ans;
int main()
{
  ll sum=0;
  int n=0;
  cin>>n;
  temp.value=9999999;
  temp.index=9999999;
  arr.push_back(temp);//占位
  for(int i=1;i<=n;i++)
  {
    cin>>temp.value;
    temp.index=i;
    arr.push_back(temp);
    sum+=temp.value;
  }
  sort(arr.begin()+1,arr.end(),cmp);
  for(int i=1;i<=n;i++)
  {
    if(i==1)
    {
      if((sum-arr.at(1).value-arr.at(2).value)==arr.at(2).value)
        ans.push_back(arr.at(1).index);
    }else
    {
      if(sum-arr.at(1).value-arr.at(i).value==arr.at(1).value)
        ans.push_back(arr.at(i).index);
    }
    
  }
  if(!ans.empty())
  {
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
    {
      cout<<ans.at(i)<<" ";
    }
  }else
    cout<<"0"<<endl<<endl;
  
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

1 − 1 =