ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2109
    알고리즘/acmicpc 2015. 2. 22. 16:09

    처음에 문제 이해못해가지고 왜 이런걸 틀리지 싶었는데 내가 틀렸다 ㅡㅡ

    QnA에서 문제를 제대로 이해하고 다시 풀어서 맞았다.


    이 문제의 핵심은 d 기간 내에는 어떤 날짜에 강연을 해도 상관 없다는거다


    그래서 3 1 1 10 2 10 2 라는 인풋이 들어오면

    정답으로 20을 출력해야한다.


    어떤 강연을 할 지 말지 결정하는 과정은 다음과 같다.


    기간내에 강연 할 수 있는 빈 시간이 있다면

    강연을 하고


    이미 강연이 다 차있다면 차있는 강연들 중에서 가장 돈을 조금 주는 강연과 비교 한 다음

    하려고 하는 강연이 더 돈을 많이 주면 가장 돈을 조금 주는 강연과 바꾸면 된다.


    생각 과정은 그리 어렵지 않은데 자료 구조를 어떤걸 쓸 것인지가 고민이었다.

    최대 10000개의 강연이 있기 때문에 생각하기 쉬운 자료구조(n*n)을 사용하면 

    시간초과가 뜬다.


    1. 그래서 나는 먼저 강연들을 기간으로 오름차순 정렬한 다음


    2. 그 기간내에 강연이 몇개 있는 지는 BIT를 이용해서 구했고(사실 이거는 안해도 되는디)


    3. 그 기간내의 강연 중 돈을 가장 조금 주는 강연은 priority queue를 통해서 구현했다.


    오름차순으로 정렬했기 때문에 기본적으로 dp로 차근차근 증가시켜 나가면 된다.


    #include<cstdio>

    #include<iostream>

    #include<algorithm>

    #include<queue>


    using namespace std;


    const int SUM_MAX = 100000001;

    int size_tree[11111];


    struct Node{

    int d, p;

    };


    bool compare(Node a, Node b)

    {

    return a.d < b.d;

    }


    int read(int idx)

    {

    int sum = 0;

    while(idx > 0)

    {

    sum += size_tree[idx];

    idx -= idx&-idx;

    }

    return sum;

    }


    void update(int idx, int val)

    {

    while(idx <= 11111)

    {

    size_tree[idx] += val;

    idx += idx&-idx;

    }

    }


    Node coll[11111];

    int d[11111];


    int main()

    {

    int n, piv= 0;

    scanf("%d", &n);


    priority_queue<int> pq;


    for(int i = 1; i <= n; i++)

    {

    scanf("%d %d", &coll[i].p, &coll[i].d);

    }

    sort(coll+1, coll+n+1, compare);


    for(int i=1;i<=n;i++)

    {

    if(read(coll[i].d) < coll[i].d)

    {

    piv++;

    update(piv, 1);

    d[piv] += coll[i].p + d[piv-1];

    pq.push(-coll[i].p);

    }

    else

    {

    if(abs(pq.top()) < coll[i].p)

    {

    d[piv] -= abs(pq.top());

    d[piv] += coll[i].p;

    pq.pop();

    pq.push(-coll[i].p);

    }

    }

    }


    printf("%d\n", d[piv]);


    return 0;

    }


    '알고리즘 > acmicpc' 카테고리의 다른 글

    2517  (0) 2015.02.26
    2568  (0) 2015.02.25
    1914  (0) 2015.02.22
    9463  (0) 2015.02.21
    2776  (0) 2015.02.21

    댓글

Designed by Tistory.