ikemonn's blog

技術ネタをちょこちょこと

【TopCoder】SRM 156 DIV2 Lv.1

SRM 156 DIV2 Lv.1

問題文概略

使っているディスク容量を、最適な形で分配する。

書いたコード(解けなかった)

  1. 全Totalの和 - 全Usedの和 = Marginを出す

  2. Usedの要素をsortする

  3. Margin - Usedの各要素

  4. 要素数 - 上記で0になるまで引けた個数

というように考えたが、これだと各hard diskの容量について考えておらずダメだった。

import java.util.Arrays;

public class DiskSpace {

    public int minDrives(int[] used, int[] total) {

        int AllUsed = 0;
        int AllTotal = 0;
        int count = 0;

        for(int x: used) {
            AllUsed += x;
        }

        for(int y: total) {
            AllTotal += y;
        }

        Arrays.sort(used);

        int Margin = AllTotal -  AllUsed;
        for(int z: used) {
            Margin = Margin - z ;
            if(Margin <= 0){
                break;
            } else {
                count++;
            }
        }

        return used.length - count;
    }

}

他の参加者のコードを読んで修正した

1.全usedの和を出す

2.Totalをsortする

3.usedの和から、Totalの各要素を降順に引いていく(v)

4.vがTotalよりも小さくなった時までの回数を数える

import java.util.Arrays;

public class DiskSpace {

    public int minDrives(int[] used, int[] total) {
        int v = 0;
        for(int x : used) {
            v += x;
        }
        Arrays.sort(total);
        int ans = 0;
        for(int i = total.length - 1; i >=0; i--) {
            if(v != 0) {
                ans++;
            }
            v -= Math.min(v, total[i]);
        }
        return ans;
    }

}

雑感

Usedの和 - Totalの各要素というように考えなければならないところを勘違いしていた。

v -= Math.min(v, total[i]);

この書き方は使えそう。