考察が済めば実装は軽い問題。
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_k
問題
N日分の宿題を他人から写すことを考える。
N日中、何回か友人宅を訪れたとする。
i日目に訪れた場合、友人からi日目含めi日目以前の宿題のうち、最大A[i]日分の宿題を写せる。
全部の宿題を写すのに、最大何日友人宅を訪れる必要があるか。
解法
P日目以前の宿題が手つかず、という状態からさかのぼって考えていこう。
初期状態でP=Nであり、Pが0以下になるまで以下を繰り返す。
P日目の宿題を行うには、P日目は必ず写させてもらわないといけない。
その際、過去A[P]日分は写すことができる。
よって、次の選択肢は(P-A[P]-1)日目~(P-1)日目のうち、もっとも写せる日数の多い日を選ぶ。
…ということを延々行う。
数値の集合のうち最大値を選ぶ処理を行うので、Priority Queueなど使おう。
int N; int A[201010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i+1]; int ret=0; priority_queue<int> PQ; int R=N; PQ.push(A[N]); while(R>0) { ret++; x=PQ.top(); PQ.pop(); if(x>=R) break; while(x--) PQ.push(A[--R]); } cout<<ret<<endl; }
まとめ
天使が悪魔の宿題を写すのか…。