글 읽기 - 그리디 문제에서 시간을 어떻게 줄여할지 모르겠어요..

astrohsy 8년 전 0

이중 for 문에서는 보석의 무게만 맞으면 바로 break해서 시간을 줄일려고 했는데. 똑같네요.

힌트 좀 부탁드립니다!

#include <cstdio>
#include <algorithm>
using namespace std;

class J {
public:
    int price;
    int weight;
};

int main() {
    J a[300000];
    int bag[300000];

    int n, k, sum = 0;
    int i, j;

    scanf("%d %d", &n, &k);
    
    for(i = 0; i<n; i++)
        scanf("%d %d", &a[i].weight, &a[i].price);
    
    for(i = 0; i<k; i++)
        scanf("%d", &bag[i]);
    
    sort(a, a+n,  [](J a, J b) { return a.price > b.price; });
    sort(bag, bag+k);
    
    //// Bag은 오름차 순으로, a는 price를 기준으로 내림차 순 정렬
    
    for(i=0; i<k; i++)
    {
        for(j=0; j<n; j++)
        {
            if(a[j].weight <= bag[i])
                break;
        }
        sum += a[j].price;
        a[j].weight = 100000000;
    }
    
    printf("%d", sum);
}

baekjoon 8년 전 2

힌트는 multiset 입니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

그리디 문제에서 시간을 어떻게 줄여할지 모르겠어요..

astrohsy 8년 전 0

baekjoon 8년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말