[今日の珂太練習場]-1138列

2237 ワード
テキストリンク

質問する



解法


この問題は比較的多くの問題をかき集めたものだ.与えられた要素を配列に配置して迅速にソートすべきかどうか、昨年のアルゴリズムの授業で似たようなタイプの問題があったと思います.
テープ上のストレージファイルは、問題と同様の方法で解決できるようです.
テープストレージファイルの問題は,グリディアルゴリズムを用いて解く問題である.
グリディアルゴリズムの詳細については、以前にブログアドレスhttps://minime00.tistory.com/22を学習した記事を参照してください.

テープに格納されているファイルの問題

  • テープにn個のファイルを格納します.
  • テープなので1次元配列と考えられます.
  • n個のファイルの長さ:L[i]-i 1番目のファイルの長さ
  • の順序で格納される場合、k番目のファイルへのアクセスに要するコストは、前のファイルの長さの和である.

    いったん保存したら、自分を読むために、私の前に余分な時間がかかります.
  • ファイルを格納する順序を調整すれば、所要時間を短縮できます.
    1)すべてのファイルが同じ頻度でアクセスされます.仮定
    2)n個のファイルからあるファイルにランダムにアクセスするために必要なコストの基数値は

    3)テープに格納する順序を変えたらどうなるでしょうか.
    ㅠ(i)は、iの場所に保存するファイルの番号です.

    ㅠ(1)=6
  • パイが順番です.
    私たちがどのようにパイ関数を設定するかによって、コストが異なります.
    質問:では、コストの値を最小限に抑えるにはどのような順序で決定すればいいのでしょうか.
    どの順番が一番いいですか?
    1番の位置にあるファイルは、ある位置にあるファイルを読み込もうとするたびに、1番の位置にあるファイルは折り畳まれて通過するしかありません.
    つまり、前の書類は何度も
    では、前の書類を成長させておけばいいです.だから、毎回何度も通るなら、小さなものを残したほうがいいです.
    長さが増える順に置けばいい
    • この問題も上記のような問題の場合に解答される.
    人々は左に自分より年上の人が何人かいることしか覚えていない.
    一列にn人立てなければならない.
    列に並ぶときは、自分の左の人数の多い人を後ろに並べ、前の方が自分の左の人数の少ない人から並んでいればいいのです.
    コード#コード#
     package backjoon;
import java.io.IOException;
import java.util.*;
public class lineup_1138 {
        Scanner sc=new Scanner(System.in);
        ArrayList<Integer>list=new ArrayList<>();
        int n;
        n=sc.nextInt();
        int a[]=new int[n+1];
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
        }
        for(int i=n;i>=1;i--){
            list.add(a[i],i);
        }
        for(int k:list){
            System.out.println(k);
        }
    }
    }
    最大サブシーケンスの合計
    (^^)/JavaマルチスレッドGuarded-SUspensionモード