[SWEA] (C++) D4 6719 성수의 프로그래밍 강좌 시청

D4 중 상당히 쉬운문제다. 조금만 생각하면 알 수 있는문제다.

다만 순서를 잘 고려해야한다. 수치가 큰 강좌 K개를 들으면 합의 MAX가 나온다.

하지만 갈수록 / 2 를 많이 해줘 큰 값을 먼저 들으면 많이 나눠서 수가 작아진다.

따라서 오름차순 정렬 후, 끝에서 K개 중 앞에서부터 강좌를 (수치가 낮은 강좌 부터) 들으면 최대치가 나온다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		int N, K; cin >> N >> K;
		vector<int> score(N);
		for (int i = 0; i < N; i++) cin >> score[i];
		
		sort(score.begin(), score.end());

		double sum = 0;
		for (int i = 0; i < K; i++)
			sum = (sum + score[N - K + i]) / 2;

		cout << '#' << test_case << ' ' << sum << '\n';
	}
	return 0;
}