BZOJ 3152: [CTSC2013]组合子逻辑 – [贪心/堆]

题目传送门(BZOJ)

题解 :

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

代码 :

#include 
#include 
#include 
#include 
#include 
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 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原创, 转载必须以链接形式注明>原文链接<