-
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;
}