UVa 1614 – Hell on the Markets [贪心]

点击打开UVa题目链接

题意

给定一些数字，给每个数字标号，要么正要么负，问是否有可能让他们的和为0

分析

从大到小依次处理就可以了。最近做题老是差那么一点点，这次又是，输出的时候忘了按照输入的顺序排序一直Wrong…..无语了

C++代码

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int val, pos, sign;
}v[102400];

int main() {
    int n, sum;
    while(cin >> n) {
        for(int i = 0; i < n; ++i)
            cin >> v[i].val, v[i].pos = i;
        sort(v, v + n, [](const Node &a, const Node &b) { return a.val > b.val; });
        sum = 0;
        for(int i = 0; i < n; ++i) {
            if(sum <= 0) { sum += v[i].val; v[i].sign = 1; }
            else { sum -= v[i].val; v[i].sign = -1; }
        }
        if(sum == 0) {
            puts("Yes");
            sort(v, v + n, [](const Node &a, const Node &b){ return a.pos < b.pos; });
            for(int i = 0; i < n; ++i)
                printf("%d%c", v[i].sign, i==n-1 ? '\n' : ' ');
        }
        else puts("No");
    }
    return 0;
}