백준 14410번 Pareto

문제 링크입니다: https://www.acmicpc.net/problem/14410

부동소수점에 유의해야하는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 금액을 내림차순으로 정렬합니다.

2. 앞에서부터 한명씩 추가하면서 누적합 비율과 인원 비율의 차를 계산하고 기록합니다.

3. 기존에 기록된 비율의 차보다 현재 비율의 차가 작아질 경우 반복문에서 탈출하고 기존 비율 A와 B를 출력합니다.

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

 

const int MAX = 300000;

 

int bank[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        long long money = 0;

        for (int i = 0; i < N; i++)

        {

                 cin >> bank[i];

                 money += bank[i];

        }

 

        //내림차순 정렬

        sort(bank, bank + N, greater<int>());

       

        //우선 맨 앞 사람 선택

        int people = 1;

        long long temp = bank[people - 1]; //금액

        double A = (double)people / N;

        double B = (double)temp / money;

        double result = B - A;

 

        while (1)

        {

                 people++;

                 temp += bank[people - 1];

                 double tempA = (double)people / N;

                 double tempB = (double)temp / money;

 

                 if (tempB - tempA > B - A)

                 {

                         B = tempB;

                         A = tempA;

                         result = B - A;

                 }

                 else

                         break;

        }

 

        printf("%.2lf\n", A * 100);

        printf("%.8lf\n", B * 100);

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~