HackerRank – Cut the Sticks

https://www.hackerrank.com/challenges/cut-the-sticks

 sticks, where the length of each stick is a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the smallest stick.

Suppose we have six sticks of the following lengths:
5 4 4 2 2 8

Then, in one cut operation we make a cut of length 2 from each of the six sticks. For the next cut operation four sticks are left (of non-zero length), whose lengths are the following:
3 2 2 6

The above step is repeated until no sticks are left.

Given the length of N$N$ sticks, print the number of sticks that are left before each subsequent cut operations.

Note: For each cut operation, you have to recalcuate the length of smallest sticks (excluding zero-length sticks).

http://blog.csdn.net/jmspan/article/details/51749533

方法：使用最小堆。

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        PriorityQueue<Integer> heap = new PriorityQueue<>(n);
        for(int i = 0; i < n; i++) {
            heap.offer(scanner.nextInt());
        }
        while (!heap.isEmpty()) {
            System.out.println(heap.size());
            int min = heap.poll();
            while (!heap.isEmpty() && min == heap.peek()) {
                heap.poll();
            }
        }
    }

http://instant.1point3acres.com/thread/139854

  static List<Integer> cutStick(int[] a) {
    List<Integer> ret = new ArrayList<>();
    Arrays.sort(a);
    int cut = -1;
    for (int i = 0; i < a.length; i++) {
      if (cut < a[i]) {
        ret.add(a.length - i);
        cut = a[i];
      }
    }
    return ret;
  }

https://sisijava.wordpress.com/2014/10/03/hackerrank-cut-the-sticks/

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int N = in.nextInt();

        int sticks[] = new int[N];

        TreeMap<Integer,Integer> h = new TreeMap<Integer,Integer>();

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

            sticks[i] = in.nextInt();

            int tmp = sticks[i];

            if(h.containsKey(tmp)){

                h.put(tmp,h.get(tmp)+1);

            }

            else{

                h.put(tmp,1);

            }

        }

        int cut[] = new int[h.size()];

        int j = 0;

        for(Integer e:h.keySet()){

            cut[j] = h.get(e);

            j++;

        }

        int output[] = new int[h.size()];

        output[0] = N;

        System.out.println(output[0]);

        for(int m=1;m<h.size();m++){

            output[m] = output[m-1]-cut[m-1];

            System.out.println(output[m]);

        }

    }

http://www.martinkysel.com/hackerrank-cut-the-sticks-solution/

Cutting every stick will result in O(N^2) which is not required. Sorting the array requires nlogn time. Python pop() requires O(1) time and importantly it does not rearrange or reallocate the array.

With each step, remove all elements from the list (actually a stack/queue) that have the same value and print the size of the remaining list.

def computeSticks(arr):

    arr.sort(reverse=True)

    while len(arr) > 0:

        print len(arr)

        block_cut = arr.pop()

        while len(arr) > 0 and arr[-1] <= block_cut:

            arr.pop()

if __name__ == '__main__':

    n = int(raw_input())

    arr = map(int, raw_input().split())

    computeSticks(arr)

Brute Force: O(n^2)

http://javaprogrammingcodes.hol.es/cut-the-sticks/

https://github.com/Transfusion/hackerrank-solutions/blob/master/Cut%20the%20sticks/Solution.java
public static void main (String[] args) {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  try {
    int stickCount = Integer.parseInt(br.readLine());
    String sticks = br.readLine();
    List<String> stickList_ = Arrays.asList(sticks.split(" "));

        List<Integer> stickList = new ArrayList<Integer>();
        for (String str : stickList_) {
            stickList.add(Integer.parseInt((String)str));
        }
     
        while (stickList.size() > 0){
          int positiveNumbers = 0;
          ListIterator<Integer> iter = stickList.listIterator();
          int currentMin = Collections.min(stickList);
          while (iter.hasNext()) {
            int next = iter.next();
            positiveNumbers++;
            iter.set(next -= currentMin);
            if (next <= 0){
              iter.remove();
            }
          }
          System.out.println(positiveNumbers);
    }
  }
  catch (IOException io){
    io.printStackTrace();
  }
 }
http://bkprogramming.blogspot.com/2015/04/hackerrank-cut-sticks-solution.html