CF 1707 C——Good Aray題解

テーマリンク: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 a 4=7 a 4=7 which equals to the sum 1+3+31+3+3.
You are given an ary a. consisting of nn integers.Your task is to print all indices j. 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 a 1 a 1,the array will look like [3,5,2][3,5,2] and it is good;

if you remove a 4 a 4,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 reulting 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 a.
The second line of the input contains nn integers a 1,a 2,…,ana 1,a 2,…,an (1≦ai≦1061≦ai≦106)—elements of the array a.
Output
In the first line print one integer kk — the number of indices j. of the array a. 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 j 1,j 2,…,jkj 1,j 2,…,jk in any order— niedices of the array a.
If there areのsuch indices in the array a,just print 00. in the first line and leave the second line empy 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

0

ノート
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 remaning elemens(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 remaning elemens(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 remaning elemens(8=3+58=3+5)
In the third example you cannot make the given array good by removing exactly one element.
 
 
入力の最初の行  2行目に入力する整数の数(数量の範囲2～2 e 5、2行目の整数範囲1～1 e 6)
2行目の与えられた配列を1つの数だけ削除します.そのうちの1つはその余りの和に等しくなります.
初歩的な考え方1:まず第二行の与えられた配列とsumを計算します.  各要素を順番に循環させる  更にsumから遍歴した元素を減算してq=sum-a[i]を得る.  qが2の倍数でない場合  明らかにそれは要求を満たしていません.  残りの要素の中に要素があれば  他の元素と表現できます.  では、すべての要素の和はその要素の二倍になります..残りの仕事は需要を満たすjを見つけるまで待つことです.   それに対応するa[i]との関係があるかどうかを判断します.  sumで引いたらqを得る.  a[i]を配列から持っていくのに相当します.  iと表記されたa[i]が存在しないため
(1)j==a[i]の場合  配列の中に少なくとも2つのa[i]が存在することを示します.  トラバースを除去したa[i]後もa[i](j)に等しい要素があるようにする.
(2)jなら!=a[i]  jの値のいずれかの数は、a配列に一度だけ現れます.二回も現れたことがありますが、配列は三つの要素しかありません.三回では無理です.  一つの数が残りの自分と同じ数値のものはないからです.  2つ  個  数をかぞえる  の和です
＊ans[a]=bは   aの値の要素はaの配列にb回現れた.
コードは以下の通りです

 1 #include
 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
",cnt);
41         for(int i=1;i<=cnt;i++)
42         {
43             printf("%d ",b[i]);
44         }
45         printf("
");
46     }
47     else 
48     printf("0
");
49     return 0;
50  } 

jには限界があります.  wa何度も  なぜタイトルが与えられた入力要素の範囲を制限するのか分かりません.
考え方2:

コードは以下の通りです

 1 # include 
 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
", 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