[editorial] Editorial - C. 인형

  • Toivoa
    Toivoa

    soyoja님의 요청도 있고, lewha0 님이 안써주셔서 대신 씁니다.
    [문제 해설]
    인형의 개수가 많기 때문에 문제에 나온대로 시뮬레이션하다가는 답이 언제 나올지는 아무도 모릅니다.
    잠시 생각해보면 나눠줄 인형의 개수를 m이라 할 때 (가장 적은 개수의 인형 수)를 한번에 나눠줄 지 판단할 수 있습니다.
    이를 이용해서 인형의 개수로 소트한 후에 앞에서부터 보면서 d[i] * (n-i) <= m (d[i]: i번 인형의 개수. 소트한 상태, n은 인형 가지수, i는 0-based index) 이라면 d[i]개를 나눠줄 수 있다는 것을 한번에 계산할 수 있습니다.
    또한 d[i] * (n - i) >m 이라면 모두에게게 d[i]개만큼 나눠줄 수 없다는 것이 되며 이 때에는 나머지 인형들은 최소 몇개를 나눠줄 수 있는지와 그 후에 남는 인형들을 계산하면 됩니다. 계산 식은 어렵지 않으니 생략합니다.
    여기에서 신경 쓰셔야 되는 것은 소트를 하기 때문에 입력된 순서가 섞인다는 점입니다. 이는 원래 입력된 index를 같이 가지고 소트하는 것을 통해 해결할 수 있습니다.
    [spoiler="소스코드 보기"]

    #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int T, n, m;
struct Doll
{
        int n, idx;
        bool operator < (const Doll& rhs) const
        {
                if (n == rhs.n) return idx < rhs.idx;
                return n < rhs.n;
        }
};
int res[100000];
Doll d[100000];
int main()
{
        scanf("%d", &T);
        while (T--)
        {
                scanf("%d%d", &n, &m);
                fill(res, res + n, -1);
                for (int i = 0; i < n; ++i)
                {
                        d[i].idx = i;
                        scanf("%d", &d[i].n);
                }
                sort(d, d + n);
                int remain, adds = 0;
                for (int i = 0; i < n; ++i)
                {
                        int x = (d[i].n) * (n - i);
                        if (x <= m)
                        {
                                res[d[i].idx] = d[i].n;
                                m -= d[i].n;
                        }
                        else
                        {
                                remain = m / (n - i);
                                adds = m - (remain * (n - i));
                                break;
                        }
                }
                if (res[0] == -1)
                        printf("%d", remain + (adds-- > 0));
                else
                        printf("%d", res[0]);
                for (int i = 1; i < n; ++i)
                {
                        if (res[i] == -1)
                                printf(" %d", remain + (adds-- > 0));
                        else
                                printf(" %d", res[i]);
                }
                printf("\n");
        }
}

    [/spoiler]
     

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    15년 전
1개의 댓글이 있습니다.
  • skelton
    skelton

    오홍 고맙습니다!


    12년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.