需要帮助提出Java中的Cake排序算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了需要帮助提出Java中的Cake排序算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4564字，纯文字阅读大概需要7分钟。

内容图文

好的,这就是我要做的

作为MCI(Mammoth Cakes Incorporated)的员工,您的工作是创造极大的
分层生日蛋糕.一个分层的生日蛋糕是通过采取小圆形蛋糕层和
将它们堆叠在一起.

为了完成你的工作,你站在一条大传送带前面
而不同大小的层在你面前经过.当你看到一个你喜欢的,你可以把它拿走
传送带,并将其添加到您的蛋糕.

您可以根据需要为蛋糕添加任意数量的图层,
只要你遵守这些规则：

将一个图层添加到蛋糕后,就无法移动. (它弄乱了结冰.)因此,层次
只能添加到你的蛋糕顶部.

每层只在你面前经过一次.你可以接受或离开它.如果你接受它,你
必须将它添加到你的蛋糕顶部.如果你离开它,它会沿传送带向下移动,
永远不会回来.

蛋糕中的每一层必须至少与下面的层一样小.你不能放置一个
较小的一层上面的较大层.

您将提前告知传送带下层的直径(以英寸为单位).
你的工作是使用这些层创建最高的蛋糕.
例如,假设以下列表表示下降的层的直径
传送带：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();

    }

}

解决方法:

正如我在几个答案中评论完全忽略了这一点,这是一个动态编程问题.

现在您已经添加了约束,很明显,在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).

如果你愿意的话,你可以这样重复,最多可以有10万个元素.

在我的计算机上,使用动态编程可以在不到20秒的时间内完成整个100 000解决方案.

这是解决问题并输出上述内容的代码.我故意添加输出语句,以便您可以看到正在发生的事情(只有相对较小的数字才能看起来非常漂亮,这只是为了得到算法的结果).

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] );
}

内容总结

以上是互联网集市为您收集整理的需要帮助提出Java中的Cake排序算法全部内容，希望文章能够帮你解决需要帮助提出Java中的Cake排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---