Morris' Blog

2012-11-27 17:45:57Morris

[PTC][201211] PB Job Allocation

留言 0 收藏 0 推薦 0

Greedy。

對價值由大排到小，依序排入理想職位，如果不足就捨棄。

#include <stdio.h>
#include <algorithm>
using namespace std;
struct ele {
    int idx, h;
};
ele A[100000];
bool cmp(ele a, ele b) {
    return a.h > b.h;
}
int main() {
    int N, Jf, Jc, Je;
    int F, C, E, H;
    int i;
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &N);
        scanf("%d %d %d", &Jf, &Jc, &Je);
        for(i = 0; i < N; i++) {
            scanf("%d %d %d %d", &F, &C, &E, &H);
            if(F > C && F > E) {
                A[i].idx = 0, A[i].h = H;
            } else if(C > F && C > E)
                A[i].idx = 1, A[i].h = H;
            else A[i].idx = 2, A[i].h = H;
        }
        sort(A, A+N, cmp);
        long long ans = 0;
        for(i = 0; i < N; i++) {
            if(A[i].idx == 0) {
                if(Jf > 0)
                    Jf--, ans += A[i].h;
            }
            if(A[i].idx == 1) {
                if(Jc > 0)
                    Jc--, ans += A[i].h;
            }
            if(A[i].idx == 2) {
                if(Je > 0)
                    Je--, ans += A[i].h;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

上一篇：[PTC][201211] PA Circular Matrix Product

下一篇：[PTC][201211] PD Happy Teachers’ Day

Morris' Blog

[PTC][201211] PB Job Allocation

你可能感興趣的文章

小事小事

用餐環境太吵之開開看江浙小館

心目中聚餐的安全牌 (9/1)

讓我感動的人事物

對話