アルゴリズム問題(六十二)トップ2017年筆記試験問題-トップ校招

2425 ワード
アルゴリズム
タイトルの説明
トップ記事の2017校募集が始まりました!今回の募集のために、私たちは規模の大きい出題チームを組織して、すべての出題者はすべていくつかの面白い問題を出して、私たちは今これらの問題をいくつかの試験に組み合わせて出たいと思って、問題を選ぶ前に、私たちは問題に対して盲審を行って、そしてすべての問題の難易度システムを決めました.1回の試験には3つの開放的な問題が含まれており、彼らの難易度が小さい頃からa,b,cと仮定すると、私たちはこの3つの問題が以下の条件を満たすことを望んでいる:a<=b<=10 b-a<=10 c-b<=10すべての出題者がnつの開放的な問題を出した.今、私たちはこのn題をいくつかの試験に分散したいと思っています(1回以上、1回しか使用できません)が、上記の条件の制限のため、3題を満たすことができない試験があるかもしれません.そのため、出題者は適切な難易度の問題を多く出して試験ごとに要求を満たす必要がありますが、私たちは出題に疲れています.私たちが少なくともいくつかの問題を出す必要があると計算できますか?
説明を入力:
            n，             。

              d1,d2,...,dn。 

    

  30%   ，1 ≤ n,di ≤ 5;

  100%   ，1 ≤ n ≤ 10^5,1 ≤ di ≤ 100。

    ，          2      20 50   ，           ：（20 20 23） （35,40,50）。

出力の説明:
       ，      。

例1
入力
4  
20 35 23 40

しゅつりょく
2

ぶんせき
数の差を判断するには,まず配列を小さいものから大きいものに並べる必要がある.後から前へ比較(dis=An-An-1)すると、3つの場合があります.
  • dis>20;

    • この場合,Anを算出する際にtimes個数が満たされる条件を満たすと仮定すると,AnとAn−1の差が20より大きいため,数を増やす必要があり,3−times個数を増やす必要がある.例えば、5、26、35の3つの数、35-26=9で、条件を満たすには、1つの数が必要で、26-5は20より大きいので、3-2=1の数が必要です.例えば、5、15、36の3つの数、35-15=21なので、3-1=2の数が必要です.
  • 10

    • この場合、数を1つ増やすだけです.5,15,26の3つの数,26−15=11のように,1つの数を増やす必要があり,増加後times=3となり,条件を満たす.
  • dis<=10;

    • この場合、現在集約されている数(times)を記録するだけでよい.
    なお、最後にtimesが3未満であるか否かを判断する必要があり、小さい場合は最後にtimes個数が揃わないことを示すため、3-times個数を増やす必要がある.例えば、5,10,15,20の4つの数は、最初の3つの数が集まった後、times=1である.5個の数しか残っていないので、3-times=2個の数が必要です.
    コード#コード#
    AC
    import java.util.Scanner;
import java.util.Arrays;
public class Main{
    
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] arr = new int[n];
        for(int i=0; i0;i--){
            int dis = arr[i] - arr[i-1];
           if(time<3){
               if(dis<=10){
                   time++;
               }else if(time == 1 && dis <= 20){
                   count++;
                   time=3;
               }else{
                   count += 3-time;
                   time = 1;
               }
           }else{
               time = 1;
           }
        }
        if(time<3){
            count += 3-time;
        }
        System.out.print(count);
    }
}

    データ圧縮のROLZ辞書符号化
    よく使われる負荷等化アルゴリズム実装