C.Good Array (思维) Codeforces Round #521 (Div. 3)
原题链接: https://codeforces.com/contest/1077/problem/C
测试样例:
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个元素。
解题思路: 我们先来判断一下这道题,删除一个元素,使得新的数组变为优秀,而优秀的条件则是某个元素值等于其他所有元素的和,那么设这一元素值为,删除的元素值为,那么原数组总和。根据这个我们发现我们如果要删除一个数,那么原数组总和减去删除数一定要等于新数组中某一元素的二倍,这样就一定满足好数组的条件。OK,我们只要对数组中所有元素做个标记,如果数组总和减去一个数再分为2倍的数有标记(即存在),那么不就可以了吗。当然,我们这里还得特判,有一张情况是不满足的,即,而又只有一个,那么明显不能组成好数组。这样这道题目就算解决完了。具体看代码。
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;
}
上一篇: 这是狮子的食物
下一篇: 香菜治发烧,这种说法是真的吗
推荐阅读
-
Codeforces Round #650 (Div. 3) B. Even Array
-
A. Add Odd or Subtract Even(思维题) Codeforces Round #624 (Div. 3)
-
Codeforces Round #686 (Div. 3) F. Array Partition
-
C.Good Array (思维) Codeforces Round #521 (Div. 3)
-
D. Cutting Out (二分查找) Codeforces Round #521 (Div. 3)
-
B. Disturbed People(模拟) Codeforces Round #521 (Div. 3)
-
B. Equal Rectangles(思维)Codeforces Round #579 (Div. 3)
-
K-periodic Garland(思维DP)(Codeforces Round #642 (Div. 3) E题)
-
Codeforces Round #650 (Div. 3) B. Even Array
-
Codeforces Round #686 (Div. 3) F. Array Partition