题目传送门(BZOJ)

题解 :

我们转化一下题目 : 选择一个数 $x$ 可以覆盖它向右的 $x$ 个数, 尽可能少的选数以覆盖整个区间
每次尽可能的向右覆盖, 并把覆盖完的点扔进大根堆中, 每次取出堆顶做下一次的覆盖
注意要特判 $n = 1$ 的情况

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 2000100;#define nc() p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++char buf[100000], *p1, *p2;inline char gc() { char ch = nc(); while(isspace(ch)) ch = nc(); return ch;}inline int rd() { int x = 0, f = 1; char ch = nc(); while(!isdigit(ch)) ch = nc(); while( isdigit(ch)) x = (((x<<2)+x)<<1)+(ch^48), ch = nc(); return x*f;}int a[N], n, ans, now;priority_queue<int> q;int main() { int T = rd(); while(T -- ) { n = rd(), ans = 0; while(!q.empty()) q.pop(); for(int i = 1; i <= n; i ++ ) a[i] = rd(); if(n == 1) {puts("0"); continue;} now = a[1]-1, ++ ans; if(!now) {puts("-1"); continue;} bool flag = 0; for(int i = 2; i <= n; i ++ ) { if(!now) { now = q.top() - 1; q.pop(); if(!now) {flag = 1; break;} ++ ans; } -- now; q.push(a[i]); } printf("%d\n", flag ? -1 : ans); }}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<