반응형
https://www.acmicpc.net/problem/17612
17612번: 쇼핑몰
입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째
www.acmicpc.net
[ 문제풀이 ]
1. priority_queue를 이용하여 계산대로 들어가는 순서를 정합니다.
2. priority_queue에서 하나씩 빼고 넣으면서 뺀 값을 vector<node> 에 넣습니다.
3. 계산대에서 나오는 순서대로 vector<node>를 정렬합니다.
4. vector<node>를 for문을 통해 돌면서 주어진 대로 계산해 ans에 저장합니다.
5. ans를 출력합니다.
[ 소스코드 ]
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 | #include<iostream> #include<queue> #include<algorithm> #define ll long long using namespace std; struct node { int K; ll num; int w; }; struct cmp { bool operator()(node right, node left) { if (left.w == right.w) return left.K < right.K; return left.w < right.w; } }; int N, k; vector<node> seq; bool cmp2(node left, node right) { if (left.w == right.w) return left.K > right.K; return left.w < right.w; } int main() { priority_queue<node, vector<node>, cmp> pq; queue<pair<ll,int>> q; scanf("%d %d", &N, &k); for (int i = 0; i < N; i++) { int b; ll a; scanf("%lld %d", &a, &b); q.push({a,b}); } for (int i = 1; i <= k; i++) { pq.push({ i,q.front().first,q.front().second }); q.pop(); if (q.empty()) break; } ll ans = 0; while (!pq.empty()) { const int K = pq.top().K; const ll num = pq.top().num; const int w = pq.top().w; pq.pop(); seq.push_back({ K,num,w }); if (!q.empty()) { pq.push({ K,q.front().first, q.front().second + w }); q.pop(); } } sort(seq.begin(), seq.end(), cmp2); for (ll i = 0; i < seq.size(); i++) { ans += seq[i].num * (i + 1); } printf("%lld", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1280번 - 나무 심기 (C++) (0) | 2023.05.20 |
|---|---|
| [ 백준 ] 2517번 - 달리기 (C++) (0) | 2023.05.19 |
| [ 백준 ] 14588번 - Line Friends (Small) (C++) (0) | 2023.05.17 |
| [ 백준 ] 9879번 - Cross Country Skiing (C++) (0) | 2023.05.16 |
| [ 백준 ] 2310번 - 어드벤처 게임 (C++) (0) | 2023.05.15 |