luogu 传送门https://www.luogu.com.cn/problem/P10077

解题思路

我们可以贪心地思考：每次寻找最小值，然后去阅读这一章。

直到阅读的章数达到 。

这样，你就可以写出一个  的暴力，拿 40 分。

但是，如果你并不满足于此，可以继续想想……

你发现每次都要求最小值，于是你想到了线段树。

可以将寻找最小值的时间优化到 。

所以，每次取到最小值之后，把它设为一个极大值，表示选过了，同时统计阅读的章数。

如果  已经被赋值成了极大值，那么说明所有章都已阅读过了，直接输出即可。

最多也是阅读  天，如果枚举过了  天，那就是无解（自己想想为什么）。

代码

#include<bits/stdc++.h>
using namespace std;int d,n,cnt;
int a[500001];
struct tree{int mn,l,r;
}tr[2000001];
void build(int u,int l,int r)
{tr[u].l=l;tr[u].r=r;tr[u].mn=a[l];if(l==r)return;int mid=l+r>>1;build(u*2,l,mid);build(u*2+1,mid+1,r);tr[u].mn=min(tr[u*2].mn,tr[u*2+1].mn);
}
void change(int u,int l,int r,int val)
{if(tr[u].l==tr[u].r){tr[u].mn=val;cnt++;return;}int mid=tr[u].l+tr[u].r>>1;if(l<=mid&&tr[u*2].mn<=cnt)change(u*2,l,r,val);if(r>mid&&tr[u*2+1].mn<=cnt)change(u*2+1,l,r,val);tr[u].mn=min(tr[u*2].mn,tr[u*2+1].mn);
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>d>>n;for(int i=1;i<=n;i++){cin>>a[i];}build(1,1,n);cnt=0;for(int i=1;i<=n;i++){change(1,1,n,INT_MAX);if(tr[1].mn==INT_MAX){cout<<i;return 0;}}cout<<-1;return 0;
}