https://www.acmicpc.net/problem/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;
}
'c++ > Baekjoon Online' 카테고리의 다른 글
백준 6198 : 옥상 정원 c++ (monotone stack) (0) | 2021.07.01 |
---|---|
백준 2258 : 정육점 c++ (0) | 2021.07.01 |
백준 8980 : 택배 C++ (0) | 2021.06.27 |
백준 1507 : 궁금한 민호 C++ (0) | 2021.06.27 |
백준 1946 : 신입사원 C++ (0) | 2021.06.26 |