[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]
     

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

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

    오홍 고맙습니다!


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