All geek questions in one place

Need help developing a cake sorting algorithm in Java

Ok that's what i need to do

As an employee of MCI (Mammoth Cakes Incorporated), your job is to create extremely large tiered cakes. A multi-layer birthday cake is made by making small circular cakes and laying them on top of each other.

To do your job, you are standing in front of a large conveyor belt while layers of different sizes pass in front of you. When you see the one you like, you can remove it from the conveyor belt and add it to your cake.

You can add as much to your cake as you want if you follow these rules:

Once a layer is added to your cake, it cannot be moved. (This will ruin the icing.) Thus, layers can only be added to the top of your cake.

Each layer passes in front of you only once. You can take it or leave it. If you do, you must add it to the top of the cake. If you leave him, he will move down the conveyor, never return.

Each layer in your cake should be at least smaller than the layer below. You cannot place a larger layer on top of a smaller one.

The diameters (in inches) of the layers descending along the conveyor belt will be indicated in advance. Your task is to create the highest cake using these layers. For example, suppose the following list represents the diameters of layers going down a conveyor belt: 8 16 12 6 6 10 5

, ( 8 ) . , ( 8 " 16" > 8 "). , ( 6 "< 8" ).

( , , ). , 4 : 8 6 6 5 , , , 5: 16 12 6 6 5

, . N, N , , . N , 0 N 100 000. 1 100 000 . , N = 0,

 Sample Input
7 8 16 12 6 6 10 5
10 45 25 40 38 20 10 32 25 18 30
10 10 9 8 7 6 5 4 3 2 1
0

Sample Output
5
6
10

:

:

import java.io.*;
import java.util.*;

public class cake
{
    private static String line;
    private static ArrayList storage = new ArrayList();
    private static Integer highestStack = 0;

    public static void main(String [] args)throws IOException
    {
          FileReader fin = new FileReader("cake.in");
        BufferedReader infile = new BufferedReader(fin);

        FileWriter fout = new FileWriter("cake.out");
        BufferedWriter outfile = new BufferedWriter(fout);


        line = infile.readLine();
        do
        {

            String[] temp = line.split(" ");
            String number;


                for(int j = temp.length-1; j!=0;  j--)
                {

                   if(Integer.parseInt(temp[j]) <= Integer.parseInt(temp[j-1]))
                   {
                       highestStack++;
                   }

                }

               storage.add(highestStack);
            //  Collections.sort(storage);



            line = infile.readLine();
        }while(!line.equals("0"));


        infile.close();
        outfile.close();

    }

}
+3
6

, , .

, , , Dynamic Programming, O (n ^ 2), - , , N 100 000, , DP (, , , -DP-).

: " " x ".

:

 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 (Best we can do using pieces: 5 )
 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 2 2 (Best we can do using pieces: 5 10 )
 0 0 0 0 0 1 2 2 2 2 2 2 2 2 2 2 2 (Best we can do using pieces: 5 10 6 )
 0 0 0 0 0 1 3 3 3 3 3 3 3 3 3 3 3 (Best we can do using pieces: 5 10 6 6 )
 0 0 0 0 0 1 3 3 3 3 3 3 4 4 4 4 4 (Best we can do using pieces: 5 10 6 6 12 )
 0 0 0 0 0 1 3 3 3 3 3 3 4 4 4 4 5 (Best we can do using pieces: 5 10 6 6 12 16 )
 0 0 0 0 0 1 3 3 4 4 4 4 4 4 4 4[5] (Best we can do using pieces: 5 10 6 6 12 16 8 )

 Tallest cake as a height of: 5

. , :

0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

, , 5 16, ( , "5" ).

'10', :

0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 2 2

, , 5 9, ( "5" ), 10 16 (5 10).

, , 100 000 .

100 000 20 , .

, . , , ( , , , ).

public static void main( String[] args ) {
    doIt( new int[] {8,16,12,6,6,10,5} );
    doIt( new int[] {0, 45, 25, 40, 38, 20, 10, 32, 25, 18, 30} ); 
    doIt( new int[] {10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1} );
}

public static void doIt( int[] r ) {
    final int[] a= new int[r.length];
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < a.length; i++) {
        max = Math.max( max, a[i] );
        a[(a.length-1)-i] = r[i];
    }
    final int[] s = new int[max+1];
    for (int i = 0; i < a.length; i++) {
        final int size = a[i];
        s[size]++;
        for (int j = size+1; j < s.length; j++) {
            s[j] = Math.max( s[j-1], s[j] );
        }
        for (int j = 0; j < s.length; j++) {
            System.out.print( " " + ((s[j]) > 9 ? "" : " ") + s[j] );
        }
        System.out.print( " (Best we can do using pieces: " );
        for (int k = 0; k <= i; k++) {
            System.out.print( a[k] + " " );
        }
        System.out.println( ")" );
    }
    System.out.println( "Tallest cake as a height of: " + s[s.length-1] );
}
+2

, , .. , .

Stack, ArrayList. , peek, cakestack .

, , , , (stack.size( )). , .., .

+1

:

10 45 25 40 38 20 10 32 25 18 30

, , []:

[10]  45   25   40   38   20   10   32   25   18   30 
 10  [45   25]  40   38   20   10   32   25   18   30
 10   45  [25]  40   38   20   10   32   25   18   30
 10   45   25  [40   38   20   10]  32   25   18   30   <-- naive tallest, 4
 10   45   25   40  [38   20   10]  32   25   18   30
 10   45   25   40   38  [20   10]  32   25   18   30
 10   45   25   40   38   20  [10]  32   25   18   30
 10   45   25   40   38   20   10  [32   25   18]  30
 10   45   25   40   38   20   10   32  [25   18]  30
 10   45   25   40   38   20   10   32   25  [18]  30
 10   45   25   40   38   20   10   32   25   18  [30]

, , :

 10  [45]  25  [40] [38]  20   10  [32] [25] [18]  30

:

 45   40   38   32   25   18
+1

, , - ( ).

public static int findMaxHeight(int[] layers) {
  int[] max = new int[layers.length];

  for(int i=layers.length - 1; i >= 0; i--) {
    int localMax = 0;
    for(int j=0; j < layers.length; j++) {
      if(layers[j] < layers[i]) {
        if(max[j] > localMax) {
          localMax = max[j];
        }
      }
    }

    max[i] = localMax + 1;    
  }

  int height = 0;

  for(int i=0; i < max.length; i++) {
    if(max[i] > height) {
      height = max[i];
    }
  }

  return height;
}

, , :

8 16 12 6 6 10 5

,

5 10 6 6 12 16 8

5, []:

5 ,
5 10 6 6 12 16 8
1

[5] max [5] = 1, 1 + 1

5 10 6 6 12 16 8
1  2

...

5 10 6 6 12 16 8
1  2 2 3  4  5 4

[1, 2, 2, 3, 4, 5, 4], 5.

, , , .

, . , , . , 1 ( ). , , , max 1.

+1

. , , : ? - :

  • , , .

  • , .

- :

tallest(remaining_layers, base_size) = # set base_size = infinity the first time
    max(
        first_layer + tallest(other_layers, size(first_layer)),
        tallest(other_layers, base_size)
    )
    where first_layer = first(remaining_layers),
          other_layers = rest(remaining_layers)

, .

, tallest other_layers . , ?

? , , , : , , , . : , . , "" ( ) .

, :

Set up a list of cakes, with one cake in it that has zero layers.
# There will be, at all times, one cake in the list of any given height.
# Starting at zero instead of one makes the iteration neater.
For each layer on the conveyor belt, working **backwards** from the last:
    Find the tallest cake in the list that fits on this layer.
    Construct the cake 'c' consisting of that cake on top of this layer.
    If there is already a cake in the list of the same height as 'c':
        If the other cake has a smaller base, throw 'c' away. # It didn't help.
        Otherwise, remove the other cake from the list. # 'c' is better.
    If we still have 'c', add it to the list.
The tallest possible cake for the input is now the tallest one in the list.
+1

, :

int[] layers = new int[] {x1,x2,x3...xn};    
int[] count = new int[layers.length];

for(int i = 1; i < layers.length; i++)
{             
       for(int j = i+1 ; j < layers.length; j++)
       {
         if ( layers[j] >= layers[i]) count[i]++; 
       }     
 }

 answer = Collections.max(Arrays.asList(count));
0

Source: https://habr.com/ru/post/1779871/

More articles:


All Articles