题目链接:http://codeforces.com/contest/1077/problem/C
题意是有一个n个元素的数组,问删除一个数,剩下的数能不能满足其中一个数等于其余剩下的数的和,如果可以保留所删除的数的位置,然后依次输出。
思路很简单,就是我们每次删除一个数后,看剩下的几个数中,最大的数是否等于剩下的数之和。实现的话就是我们把每个数的位置存起来,然后降序排序,然后枚举实现删除的操作就好了。如果直接n^2遍历的话会超时...
AC代码:
#include <bits/stdc++.h>
#define maxn 200005
#define ll long long
using namespace std;
struct Node{
ll num,id;
}Edge[maxn];
int n;
bool cmp(Node a, Node b){
return a.num > b.num;
}
int main()
{
ll sum = 0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&Edge[i].num);
sum += Edge[i].num;
Edge[i].id = i;
}
vector<ll> v;
sort(Edge + 1, Edge + 1 + n, cmp);
for(int i=1;i<=n;i++){
ll xx = sum - Edge[i].num;
if(i == 1 && xx - Edge[i+1].num == Edge[i+1].num){
v.push_back(Edge[i].id);
}
if(i != 1 && xx - Edge[1].num == Edge[1].num){
v.push_back(Edge[i].id);
}
}
printf("%d\n",v.size());
for(int i=0;i<v.size();i++){
printf("%lld ",v[i]);
}
return 0;
}