CF1077C——Good Array题解

浅浅的花香味﹌ 2023-10-11 09:56 32阅读 0赞

题目链接：[http://codeforces.com/problemset/problem/1077/C][http_codeforces.com_problemset_problem_1077_C]

Let's call an array good if there is an element in the array that equals to the sum of all other elements. For example, the array a=\[1,3,3,7\]a=\[1,3,3,7\] is good because there is the element a4=7a4=7 which equals to the sum 1\+3\+31+3+3.

You are given an array aa consisting of nn integers. Your task is to print all indices jj of this array such that after removing the jj-th element from the array it will be good (let's call such indices nice).

For example, if a=\[8,3,5,2\]a=\[8,3,5,2\], the nice indices are 11 and 44:

*  if you remove a1a1, the array will look like \[3,5,2\]\[3,5,2\] and it is good;
 *  if you remove a4a4, the array will look like \[8,3,5\]\[8,3,5\] and it is good.

You have to consider all removals independently, i. e. remove the element, check if the resulting array is good, and return the element into the array.

Input

The first line of the input contains one integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the number of elements in the array aa.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1061≤ai≤106) — elements of the array aa.

Output

In the first line print one integer kk — the number of indices jj of the array aa such that after removing the jj-th element from the array it will be good (i.e. print the number of the nice indices).

In the second line print kk distinct integers j1,j2,…,jkj1,j2,…,jk in any order — niceindices of the array aa.

If there are no such indices in the array aa, just print 00 in the first line and leave the second line empty or do not print it at all.

Examples

Input

5
    2 5 1 2 2

Output

3
    4 1 5

Input

4
    8 3 5 2

Output

2
    1 4

Input

5
    2 1 2 4 3

Output

Note

In the first example you can remove any element with the value 22 so the array will look like \[5,1,2,2\]\[5,1,2,2\]. The sum of this array is 1010 and there is an element equals to the sum of remaining elements (5=1\+2\+25=1+2+2).

In the second example you can remove 88 so the array will look like \[3,5,2\]\[3,5,2\]. The sum of this array is 1010 and there is an element equals to the sum of remaining elements (5=3\+25=3+2). You can also remove 22 so the array will look like \[8,3,5\]\[8,3,5\]. The sum of this array is 1616 and there is an element equals to the sum of remaining elements (8=3\+58=3+5).

In the third example you cannot make the given array good by removing exactly one element.

题意：输入的第一行  为第二行所要输入的整数的数量（数量的范围2~2e5，第二行整数范围1~1e6）

将第二行所给数组去掉一个数 使得其中一个数会等于其余数的和

初步思路1：先算出第二行所给数组的和sum  依次循环数组每一个元素  再用sum减去所遍历到的元素得q=sum-a\[i\]  如果q不是2的倍数  显然它不满足要求（因为如果去掉a\[i\]  剩下的元素中如果存在一个元素  可以用其他元素的和表示  那么剩下所有元素的和等于那个元素的两倍）。。。。剩下的工作就是 等到找到求出满足要求的j   再判断它是否和所对应的a\[i\]的关系（为什么呢？因为我们遍历到的a\[i\]  用sum减去以后得到q  相当于将a\[i\]从数组中拿走  即不存在一个下标为i的a\[i\]）所以

（1）如果j==a\[i\]  说明数组中存在至少两个a\[i\]  使得去掉遍历的a\[i\]后仍有元素等于a\[i\]（即j）；

（2）如果j！=a\[i\]  那么要么数值为j的数在a数组中只出现过一次；或者出现过两次但是数组只有三个元素；出现三次就不太可能了  因为不存在有一个数等于剩下的和自己相等数值的  两  个  数  的和。

\*ans\[a\]=b表示   数值为a的元素在a数组中出现了b次

代码如下：

1 #include<stdio.h>
     2 #include<string.h>
     3 typedef long long LL;
     4 const int maxn=2e5+10;
     5 int t,cnt,a[maxn],flag,ans[1000000+10],b[maxn];
     6 LL sum;
     7 void init()
     8 {
     9     memset(ans,0,sizeof(ans));
    10     memset(b,0,sizeof(b));
    11     sum=cnt=flag=0;
    12 }
    13 int main()
    14 {
    15     init();
    16     scanf("%d",&t);
    17     for(int i=1;i<=t;i++)
    18     {
    19         scanf("%d",&a[i]);
    20         sum+=a[i];
    21         ans[a[i]]++;
    22     }
    23     for(int i=1;i<=t;i++)
    24     {
    25         LL q=sum-a[i];
    26         LL j=q/2;
    27         if(q%2)continue;
    28         if(j<=1000000)//这条不能少 少了会test6过不了 
    29         {
    30             //（1）如果j==a[i]  说明数组中存在至少两个a[i]  使得去掉遍历的a[i]后仍有元素等于a[i]（即j）；
    31             //（2）如果j！=a[i]  那么要么数值为j的数在a数组中只出现过一次；或者出现过两次但是数组只有三个元素。
    32             if(j==a[i]&&ans[j]>1||ans[j]==1&&a[i]!=j||t==3&&ans[j]==2&&a[i]!=j)
    33             {
    34                 b[++cnt]=i;flag=1;
    35             }
    36         }     
    37     }
    38     if(flag)
    39     {
    40         printf("%d\n",cnt);
    41         for(int i=1;i<=cnt;i++)
    42         {
    43             printf("%d ",b[i]);
    44         }
    45         printf("\n");
    46     }
    47     else 
    48     printf("0\n");
    49     return 0;
    50  }

被j的要有范围坑了  wa了好多次  还是不知道为什么要限制题目给定的输入元素的范围。

思路2：

![1591144-20190730112059066-2017304772.png][]

代码如下：

1 # include <bits/stdc++.h>
     2 
     3 # define ll long long
     4 
     5 struct p
     6 {
     7     int id;
     8     ll x;
     9 };
    10 
    11 p a[200001];
    12 
    13 int cmp(p x, p y){
        return x.x < y.x;}
    14 
    15 std::vector<int> vec;
    16 
    17 int main()
    18 {
    19     int n;
    20     ll sum = 0;
    21     scanf("%d", &n);
    22     for(int i = 1; i <= n; i++)
    23         scanf("%d", &a[i].x), a[i].id = i, sum += a[i].x;
    24     std::sort(a + 1, a + n + 1, cmp);
    25     for(int i = 1; i <= n; i++)
    26     {
    27         if(i != n)//情况1
    28         {
    29             if(sum - a[n].x - a[i].x == a[n].x)
    30                 vec.push_back(a[i].id);
    31         }
    32         else //情况2
    33         {
    34             if (sum - a[n - 1].x - a[i].x == a[n - 1].x)
    35                 vec.push_back(a[i].id);
    36         }
    37     }
    38     if(vec.size())
    39     {
    40         printf("%d\n", vec.size());
    41         for(int i = 0; i < vec.size(); i++)
    42             printf("%d ", vec[i]);
    43     }
    44     else    
    45         printf("0");
    46     return 0;
    47 }

如有错误请多多指正，谢谢阅读！

转载于:https://www.cnblogs.com/Mingusu/p/11268938.html

[http_codeforces.com_problemset_problem_1077_C]: http://codeforces.com/problemset/problem/1077/C
[1591144-20190730112059066-2017304772.png]: https://img2018.cnblogs.com/blog/1591144/201907/1591144-20190730112059066-2017304772.png