백준 1461 : 도서관 C++

https://www.acmicpc.net/problem/1461

1461번: 도서관

 

풀이

1. 일단 당연히 음수 쪽이랑, 양수쪽이랑 분리

 

2. m 개씩 멀리서부터 한 그룹으로 묶기

-> 묶으면서 그 그룹의 최대값 저장해두기

 

3. 가장 먼 그룹 제외하고 answer += 각 그룹의 최대값 *2

 

4. answer += 가장 먼 그룹의 최댓값

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int answer = 0;
vector<int> pluss;
vector<int> minuss;

bool cmp(int a, int b)
{
	return a > b;
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;
		if (input < 0)
			minuss.push_back(input);
		else
			pluss.push_back(input);
	}
	sort(minuss.begin(), minuss.end());
	sort(pluss.begin(), pluss.end(),cmp);

	vector<int> maxes;

	for (int i = 0; i < minuss.size();)
	{
		maxes.push_back(abs(minuss[i]));
		i += m;
	}

	for (int i = 0; i < pluss.size();)
	{
		maxes.push_back(pluss[i]);
		i += m;
	}
	sort(maxes.begin(), maxes.end(), cmp);

	answer += maxes[0];
	for (int i = 1; i < maxes.size(); i++)
	{
		answer += 2*maxes[i];
	}

	cout << answer << endl;
	return 0;
}