Hackで稼いでだいぶレートが上がった回。
http://codeforces.com/contest/1190/problem/A
問題
1~Nの整数が順に並んでいる。
これらは先頭からK個ごとに区切られ、各区切りはページとして扱われる。
このうち、消すべき数字M個が指定される。
消すときは以下の手順で消される。
- 消すべき数字のうち、まだ消されていない最小の数字を選択する。
- その数字と、同じ位置ページ内にある数字をまとめて消す。
- 空いた場所は詰める。ページの区切りも再調整される。
消すべき数字がすべて消えるまで、何手かかるか答えよ。
解法
消える順は常に小さい順である。
よって、これまで何個数字が消えたかを覚えておけば、次に消えるべき数字がわかるし、その数字のいるページも簡単に計算できるので、合わせて何個数字が消えるかもわかる。
あとは単純にシミュレーションを繰り返すだけ。
O(M)で解ける。
ll N,M,K; ll P[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>K; FOR(i,M) { cin>>P[i]; P[i]--; } int num=0; ll dis=0; int cur=0; while(cur<M) { ll page=(P[cur]-dis)/K; while(cur<M && (P[cur]-dis)/K==page) cur++; num++; dis=cur; } cout<<num<<endl; }
まとめ
Codeforces書かなさすぎて3か月半もビハインドしてしまっている…。