Codeforces

https://codeforces.com/contest/1191/problem/C
一开始想象了一下，既然每次删除都是往前面靠，那么好像就是页数*页容量+空位数=最多容纳到的坐标。
至于为什么呢？好像是每次都会删除干净的原因，从第一页开始考虑，第一页可以容纳到5，这个很显然。
删除之后有2个空位，然后可以容纳到7。再把7也删除，就可以容纳到8。

那么每次就暴力删除特殊元素就可以了，反正最多就是m个。

问题在于翻页的时候不能够简单的curpage++，这样必定翻车。我是直接二分，因为顶多就是分m次logn，非常小。看了别人的可以每次O(1)得到。
具体的做法是：比如现在取不出队首的元素a[i]了，直接翻到哪一页呢？最多容纳到的坐标要比a[i]大，用a[i]减去空位数，就可以得到它当前的坐标，记做b[i]，那么所需的页数就是包含b[i]的最小的k的倍数，自然就是(b[i]+k-1)/k*k。

不过复杂度都是对的，有个数组越界bug但是却没事？

``` #include using namespace std; typedef long long ll;

ll n, k;
int m;
int sumdiscard = 0;
ll curpage = 1;
int ans = 0;
int _begin = 1;
ll max_delta;

ll a[100005];

ll find_delta() {
ll l = 1, r = max_delta;
while(1) {
ll m = l + r >> 1;
if(m == l) {
if(k * (curpage + l) + sumdiscard >= a[_begin]) {
//足够大
return l;
} else {
return r;
}
}
if(k * (curpage + m) + sumdiscard >= a[_begin]) {
//足够大
r = m;
} else {
//不够大
l = m + 1;
}
}
}

int main() {
scanf("%lld%d%lld", &n, &m, &k);
max_delta = (n + k - 1) / k;
for(int i = 1; i <= m; i++) {
scanf("%lld", &a[i]);
}
while(sumdiscard < m) {
if(curpage * k + sumdiscard >= a[_begin]) {
//至少有一个特殊元素要被删除
int cnt = 0;
while(curpage * k + sumdiscard >= a[_begin]) {
_begin++;
cnt++;
}
sumdiscard += cnt;
ans++;
} else {
curpage += find_delta();
//效率可能过低
}
}
printf("%d ", ans);
}

</details>

当然既然每次都是去k的倍数干脆curpage就不用乘k了。

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a[100005];

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
    //freopen("Yinku.out", "w", stdout);
#endif // Yinku
    ll n, k;
    int m;
    while(~scanf("%lld%d%lld", &n, &m, &k)) {
        for(int i = 1; i <= m; i++) {
            scanf("%lld", &a[i]);
        }
        int sumdiscard = 0, ans = 0, _begin = 1;
        ll curpage = k;
        while(sumdiscard < m) {
            if(curpage + sumdiscard >= a[_begin]) {
                //至少有一个特殊元素要被删除
                int cnt = 0;
                while(_begin <= m && curpage  + sumdiscard >= a[_begin]) {
                    _begin++;
                    cnt++;
                }
                sumdiscard += cnt;
                ans++;
            } else {
                curpage = (a[_begin] - sumdiscard + k - 1) / k * k ;
            }
        }
        printf("%d
", ans);
    }
}