풍선
문제
전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다.
풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다.
풍선은 방 A와 방 B에 보관되어 있다.
대회에 참가한 팀의 수는 총 N개이고, 앉아있는 자리는 서로 다르다.
어떤 팀은 방 A에 가깝고, 어떤 팀은 B에 더 가깝다.
각 팀에게 달아줘야 하는 풍선의 수와 방 A와 B로부터의 거리가 주어진다.
이때, 모든 풍선을 달아주는데 필요한 이동 거리의 최솟값을 출력한다.
대회에서 풍선을 달아주는 사람은 매우 많고, 풍선은 한 가지 색상을 여러 개 달아준다고 가정한다.
풍선을 달기 위해 이동해야하는 거리는 팀이 A와 B로부터 떨어진 거리와 같다.
풍선을 달아주는 사람은 한 번에 풍선 하나만 들고 이동할 수 있다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과
방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000)
다음 N개 줄에는 팀에게 달아줘야하는 풍선의 수 K와 방 A로부터 떨어진 거리 DA, B로부터 떨어진 거리 DB (0 ≤ DA, DB ≤ 1,000)가 주어진다.
풍선이 부족한 경우는 없다. 즉, Σi Ki ≤ A+B.
입력의 마지막 줄에는 0이 세 개 주어진다.
출력
각 테스트 케이스에 대해서, 모든 팀에게 풍선을 달아주기 위해 필요한 이동 거리의 최솟값을 한 줄에 하나씩 출력한다.
이때, 풍선을 달아주고 방 A나 B로 돌아오는 거리는 포함하지 않는다.
즉, 방 A와 B에서 팀으로 이동하는 거리만 포함한다.
1
2
3
4
5
6
7
8
9
예제 입력 1
3 15 35
10 20 10
10 10 30
10 40 10
0 0 0
예제 출력 1
300
풀이
MCMF라는 유체 알고리즘 문제라는데 그리디로 풀었다.
구현이 좀 길긴한데 단순해서 생각난 대로 짰더니 잘 됐다.
아이디어는 A거리 - B거리의 절댓값으로 정렬해서 A에 가는게 이득이면 A에 넣고,
B에 가는게 이득이면 B에 넣고 한 쪽이 꽉차면 남은거 전부 다른 쪽에서 가져오게 했다.
총 풍선의 개수가 구할 풍선의 개수보다 작다고 써있기 때문에 가능하다.
입력 케이스가 왜 0 0 0으로 끝나나 했는데 while(1)로 여러 테스크 케이스를 받아야 풀리는 문제였다.
시간초과도 안 나는게 O(N)으로 종료된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <array>
#include <tuple>
#include <algorithm>
#include <math.h>
using namespace std;
int al = 0;
int max = 10001;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int ar[102][102] = {0};
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while (1)
{
long long a, b, c, total = 0;
long long block = 0;
int n, m, k;
int bal, ad, bd;
cin >> n >> a >> b;
if(n+a+b==0)break;
vector<tuple<int, int, int>> v;
vector<pair<int, int>> index1;
vector<pair<int, int>> index2;
for (int i = 0; i < n; i++)
{
cin >> bal >> ad >> bd;
v.push_back({bal, ad, bd});
if (ad - bd >= 0)
index1.push_back({ad - bd, i});
if (ad - bd < 0)
index2.push_back({ad - bd, i});
}
sort(index1.begin(), index1.end(), greater<>()); // 양수면 큰 순서 //b에 가야함
sort(index2.begin(), index2.end()); // 음수면 작은 순서 //a에가야함
int check_a = 0, check_b = 0;
for (int i = 0; i < index1.size(); i++)
{
if (b >= get<0>(v[index1[i].second]))
{
b -= get<0>(v[index1[i].second]);
total += get<0>(v[index1[i].second]) * get<2>(v[index1[i].second]);
get<0>(v[index1[i].second]) = 0;
}
else
{
total += get<2>(v[index1[i].second]) * b;
get<0>(v[index1[i].second]) -= b;
b = 0;
check_b = 1;
}
}
for (int i = 0; i < index2.size(); i++)
{
if (a >= get<0>(v[index2[i].second]))
{
a -= get<0>(v[index2[i].second]);
total += get<0>(v[index2[i].second]) * get<1>(v[index2[i].second]);
get<0>(v[index2[i].second]) = 0;
}
else
{
total += get<1>(v[index2[i].second]) * a;
get<0>(v[index2[i].second]) -= a;
a = 0;
check_a = 1;
}
}
if (check_a)
{ // a가 0이면 b에 다 줘야함.
for (int i = 0; i < index1.size(); i++)
{
total += get<0>(v[index1[i].second]) * get<2>(v[index1[i].second]);
}
for (int i = 0; i < index2.size(); i++)
{
total += get<0>(v[index2[i].second]) * get<2>(v[index2[i].second]);
}
}
else if (check_b)
{ // b가 0이면 a에 다 줘야함.
for (int i = 0; i < index1.size(); i++)
{
total += get<0>(v[index1[i].second]) * get<1>(v[index1[i].second]);
}
for (int i = 0; i < index2.size(); i++)
{
total += get<0>(v[index2[i].second]) * get<1>(v[index2[i].second]);
}
}
// 음수면 a쪽
// 양수면 b쪽
cout << total << '\n';
}
return 0;
}