codeforces #610 div2 B2 - K for the Price of One (구현)

https://codeforces.com/contest/1282/problem/B2

빡구현

 

<문제설명>

초기 돈 p와 세트로 살 수 있는 묶음단위 k, 최대 2e5개의 물품 가격이 주어질 때, 최대한 많은 물품을 구하는 경우 몇개를 사는지 구하는 문제. 한번 물건을 살 땐 단 한개를 사거나 딱 k개를 사야 한다. k개 묶음을 살 땐 가장 비싼 물품에 대해만 돈을 내면 된다.

 

<풀이>

돈 6, 묶음단위 3, 가격 2 3 4 5 7 8이 주어질 때를 생각해보면.. (초기돈은 신경쓰지 말자)

물건 1개 살 때 -> (2)      가격:2

물건 2개 살 때 -> (2),(3)  가격:5 -> 일단 신경쓰지 않는다. 더 싼 값으로 더 많이 살 수 있기 때문.

물건 3개 살 때 -> (2,3,4)  가격:4

물건 4개 살 때 -> (2),(3,4,5) 가격:7

물건 5개 살 때 -> (2),(3), (4,5,7)   가격:12

물건 6개 살 때 -> (2,3,4) (5,7,8)  가격:12

 

돈을 더 내는 것을 감수하고 단 한개씩 사는 경우도 고려해야 하는 문제이므로 좀 까다롭다. 예를들면

돈 5 묶음단위 3 가격 1 1 2 2 2를 생각해보면..

(1),(1),(2,2,2)로 5개 모두를 사는 경우도 있기 때문!

 

단 한 개씩 사야만 하는 경우는 정렬된 가격의 앞에서부터 최대 k-1개 사는 것이 최적이다. 나머지는 최대한 세트구매해야 한다.

 

한 개씩 구입하는 물품이 1개일때.. 2개일때.. 3개일때.. k-1개일때..를 순회하는 것으로 바깐 루프를 구성하고, 안쪽루프에선 최대한 세트구매할 때의 가격과 수량을 컨트롤한다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 2e5 + 5;

int main() {
	int tt; cin >> tt;
	while (tt--) {
		int n, p, k, a[MAX], psum[MAX];
		cin >> n >> p >> k;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		sort(a, a + n);
		for (int i = 0; i < n; i++) {
			psum[i] = i == 0 ? a[i] : psum[i - 1] + a[i];
		}

		int ans = 0;
		for (int i = 0; i <= k; i++) {
			int sum = i > 0 ? psum[i - 1] : 0, cnt = 0;
			if (sum > p) break;

			for (int j = i + k - 1; j < n; j += k) {
				if (sum + a[j] <= p) {
					sum += a[j];
					cnt += k;
				}
				else break;
			}
			ans = max(ans, i + cnt);
		}
		cout << ans << '\n';
	}
}