Codeforces Round #493 (Div. 2) A. Balloons 贪心水题

由于是输出任意一组解,可以将价值从小到大进行排序,第一个人只选第一个,第二个人选其余的。再比较一下第一个人选的元素和第二个人所选元素和是否相等即可。由于已将所有元素价值从小到大排过序,这样可以保证在有解的情况下一定可以构造出可行解。

Code:

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100000 + 3;
int a[maxn], A[maxn];
bool cmp(int i,int j) { return a[i] < a[j];}
int main()
{
int n;
cin >> n;
for(int i = 1;i <= n; ++i){ cin >> a[i]; A[i] = i; }
if(n == 1) { cout << -1 ; return 0; }
sort(A + 1, A + 1 + n,cmp);
int sum = 0;
for(int i = 2; i <= n; ++i) sum += a[A[i]];
if(sum == a[A[1]]) cout << -1;
else cout << 1 << "\n" << A[1] ;
return 0;
}
上一篇:hdu_2124 Flying to the Mars & hdu_1800 Repair the Wall 贪心水题


下一篇:no route to host