2017バイトジャンプ秋招プログラミング問題-トップ校招
10241 ワード
タイトル説明トップ記事の2017校募集が始まりました!今回の募集のために、私たちは規模の大きい出題チームを組織して、すべての出題者はすべていくつかの面白い問題を出して、私たちは今これらの問題をいくつかの試験に組み合わせて出たいと思って、問題を選ぶ前に、私たちは問題に対して盲審を行って、そしてすべての問題の難易度システムを決めました.1回の試験には3つの開放的な問題が含まれており、彼らの難易度が小さい頃からa,b,cと仮定すると、私たちはこの3つの問題が以下の条件を満たすことを望んでいる:a<=b<=10 b-a<=10 c-b<=10すべての出題者がnつの開放的な問題を出した.今、私たちはこのn題をいくつかの試験に分散したいと思っています(1回以上、1回しか使用できません)が、上記の条件の制限のため、3題を満たすことができない試験があるかもしれません.そのため、出題者は適切な難易度の問題を多く出して試験ごとに要求を満たす必要がありますが、私たちは出題に疲れています.私たちが少なくともいくつかの問題を出す必要があると計算できますか?
入力記述入力の最初の行には、現在すでに出力されている問題の数を示す整数nが含まれている.2行目は,各問題の難易度係数d 1,d 2,...,dnを与える.データ範囲は30%のデータに対して、1≦n、di≦5である.100%のデータに対して,1≦n≦10^5,1≦di≦100であった.サンプルでは、2つの難易度がそれぞれ20と50の問題を追加することで、2つの試験に組み合わせることができます:(20,23)と(35,40,50).
出力記述出力は、1行、すなわち求められた答えのみを含む.
例1入力4 20 35 23 40出力2
実現構想変数goodは1に初期化され,現在条件に合致する問題数を示し,カウント範囲は1−3である.配列aは問題を格納するのが難しい.まず、問題の難易度を小さい順に並べ替えます.それから状況に分けます:(1)各テーマの難易度はすべて条件に合います:20 23 30 31両比較して、a[i+1]-a[i]<=10に合っているかどうかを見て、もし合っているならばgood++です.goodが3の場合、一連の問題を構成することができるので、goodは再び0になり、条件に合った問題を再計算します.a配列を巡回した後に実行する(4).(2)good=2の場合:20 23 35 40,23,35が条件を満たしていない場合、追加する必要がある問題数divergenceは:(35-23)/10=1、35を40,23を20に変更すると、追加する必要がある問題数は:(40-20)/10-1=1、すなわち、追加難易度が30の問題を1セット構成することができ、20 23(30)35 40である.このときgoodの変化は、good=(good+divergence)%3+1=(2+1)%3+1=1であり、加算1は後の35を含むためであり、このときgood=3と計算されると、付与値は1である.その後、35と40を比較し続け、条件に合致し、good++、このときgood=2とします.a配列を巡回した後に(4)を実行して、3-good=1を得て、全部で2つのテーマを増やす必要があります.(3)good=1の場合:23,35,40,41,23,35が条件を満たしていない場合,追加する必要がある問題数divergenceを算出することは,(2)使用する方法と同様であるが,good=(good+divergence)%3+1=(1+1)%3+1=3,(2)使用する方法と同様であり,この場合の問題難易度分布は:23(30)35,40,41である.違いは、計算されたgood=3であれば、0に割り当てられます.a配列を巡回した後に実行する(4).(4)上記の3つのいずれの場合においても,最後に問題対比を遍歴した後,good%3が0に等しくなければ,すなわち問題目数が3の倍数ではない場合,増加する必要がある問題数は:3−goodである.
コード実装
入力記述入力の最初の行には、現在すでに出力されている問題の数を示す整数nが含まれている.2行目は,各問題の難易度係数d 1,d 2,...,dnを与える.データ範囲は30%のデータに対して、1≦n、di≦5である.100%のデータに対して,1≦n≦10^5,1≦di≦100であった.サンプルでは、2つの難易度がそれぞれ20と50の問題を追加することで、2つの試験に組み合わせることができます:(20,23)と(35,40,50).
出力記述出力は、1行、すなわち求められた答えのみを含む.
例1入力4 20 35 23 40出力2
実現構想変数goodは1に初期化され,現在条件に合致する問題数を示し,カウント範囲は1−3である.配列aは問題を格納するのが難しい.まず、問題の難易度を小さい順に並べ替えます.それから状況に分けます:(1)各テーマの難易度はすべて条件に合います:20 23 30 31両比較して、a[i+1]-a[i]<=10に合っているかどうかを見て、もし合っているならばgood++です.goodが3の場合、一連の問題を構成することができるので、goodは再び0になり、条件に合った問題を再計算します.a配列を巡回した後に実行する(4).(2)good=2の場合:20 23 35 40,23,35が条件を満たしていない場合、追加する必要がある問題数divergenceは:(35-23)/10=1、35を40,23を20に変更すると、追加する必要がある問題数は:(40-20)/10-1=1、すなわち、追加難易度が30の問題を1セット構成することができ、20 23(30)35 40である.このときgoodの変化は、good=(good+divergence)%3+1=(2+1)%3+1=1であり、加算1は後の35を含むためであり、このときgood=3と計算されると、付与値は1である.その後、35と40を比較し続け、条件に合致し、good++、このときgood=2とします.a配列を巡回した後に(4)を実行して、3-good=1を得て、全部で2つのテーマを増やす必要があります.(3)good=1の場合:23,35,40,41,23,35が条件を満たしていない場合,追加する必要がある問題数divergenceを算出することは,(2)使用する方法と同様であるが,good=(good+divergence)%3+1=(1+1)%3+1=3,(2)使用する方法と同様であり,この場合の問題難易度分布は:23(30)35,40,41である.違いは、計算されたgood=3であれば、0に割り当てられます.a配列を巡回した後に実行する(4).(4)上記の3つのいずれの場合においても,最後に問題対比を遍歴した後,good%3が0に等しくなければ,すなわち問題目数が3の倍数ではない場合,増加する必要がある問題数は:3−goodである.
コード実装
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
int sum = 0;
int good = 1;
for (int i = 0; i < a.length - 1; i++) {
if(good == 3)good = 0; // （1） （3）
if(a[i+1] - a[i] <= 10 )good++; // （1）
else // （2） （3）
{
int goodCopy = good; // good
int temp, divergence = a[i+1] - a[i];
// a[i+1] a[i] ， 10， a[i]， a[i]， 1
if(divergence % 10 == 0)temp = divergence / 10 - 1;
else temp = divergence / 10;
sum+= temp; //
good = (good + temp) % 3 + 1; //
if(goodCopy == 2)good = 1; // （2）
}
}
if(good % 3 != 0)sum += (3 - good); // （4）
System.out.println(sum);
}
}
}