欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C.Good Array (思维) Codeforces Round #521 (Div. 3)

程序员文章站 2022-06-04 19:42:40
...

原题链接: https://codeforces.com/contest/1077/problem/C

C.Good Array (思维) Codeforces Round #521 (Div. 3)
测试样例:

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

Note
In the first example you can remove any element with the value 2 so the array will look like [5,1,2,2]. The sum of this array is 10 and there is an element equals to the sum of remaining elements (5=1+2+2).
In the second example you can remove 8 so the array will look like [3,5,2]. The sum of this array is 10 and there is an element equals to the sum of remaining elements (5=3+2). You can also remove 2 so the array will look like [8,3,5]. The sum of this array is 16 and there is an element equals to the sum of remaining elements (8=3+5).
In the third example you cannot make the given array good by removing exactly one element.

题意: 当一个数组中的某个元素值等于其他所有元素的和,我们称这个数组是“优秀”的。比如[1,3,3,7],是优秀的,因为7=1+3+3。
给你一个包含 n 个元素的数组 a ,对于某一个下标 j (1<=j<=n),当删除这个元素后,可能使新的数组变为“优秀”的。比如[1,3,3,1,7],当删除a[1]或者a[4]时,这个数组就是“优秀”的,你的任务是找到所有满足条件的下标 j 。
注意:每次删除都是独立的,每次删除都是由n个元素变为n-1个元素。

解题思路: 我们先来判断一下这道题,删除一个元素,使得新的数组变为优秀,而优秀的条件则是某个元素值等于其他所有元素的和,那么设这一元素值为aa,删除的元素值为bb,那么原数组总和sum=a2+bsum=a*2+b。根据这个我们发现我们如果要删除一个数,那么原数组总和减去删除数一定要等于新数组中某一元素的二倍,这样就一定满足好数组的条件。OK,我们只要对数组中所有元素做个标记,如果数组总和减去一个数再分为2倍的数有标记(即存在),那么不就可以了吗。当然,我们这里还得特判,有一张情况是不满足的,即suma=2asum-a=2*a,而aa又只有一个,那么明显不能组成好数组。这样这道题目就算解决完了。具体看代码。

AC代码:

/*
*邮箱:aaa@qq.com
*blog:https://me.csdn.net/hzf0701
*注:文章若有任何问题请私信我或评论区留言,谢谢支持。
*/
#include<bits/stdc++.h>	//POJ不支持

#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量,a为初始值,n为界限值,递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量, a为初始值,n为界限值,递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int inf = 0x3f3f3f3f;//无穷大
const int maxn = 2e5+2;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************分割线,以上为自定义代码模板***************************************//

int n,a[maxn],b[maxn];
int main(){
	//freopen("in.txt", "r", stdin);//提交的时候要注释掉
	IOS;
	while(cin>>n){
		map<ll,int> vis;
		ll sum=0;
		int cnt=0;
		rep(i,1,n){
			cin>>a[i];
			vis[a[i]]++;
			sum+=a[i];
		}
		rep(i,1,n){
			if((sum-a[i])%2)continue;//删除这个数剩下的数总和为奇数,说明不可能成立。
			if(vis[(sum-a[i])/2]){
				if(vis[a[i]]-1==0&&sum==3*a[i])continue;//特判,即只存在一个a[i],而剩下的数为两个a[i],那么明显不行。
					b[cnt++]=i;
			}
		}
		cout<<cnt<<endl;
		rep(i,0,cnt-1)cout<<b[i]<<" ";
		if(cnt)cout<<endl;
	}
	return 0;
}