TJ 2 P4505

· · 题解

破题 & 承题

题面有毒，用正常人的语言翻译一下，就是说：

在给出的数中选一定量的数。对于这之中的一个数 x 而言，它可以覆盖该数列当前指针中的位置向后 x - 1 的距离。要求的是覆盖整个数列所需要的最少的数的个数。

起讲 & 入手

很显然，考虑贪心。

用优先队列来记录，用变量 counter 来表示指针还能向前推进多少距离。

读入下一个数前，先判定 counter 是否为零，如果为零，那么需要从优先队列中选出下一个数，并将其推出，如果选不出，那么就标记无解；如果不为零，那么 counter 减少一，处理完后再把下一个数推入优先队列。

于是核心代码如下：

if (reader>>n, n == 1){//reader是快读
    printf("%d\n", reader?0:-1);
    continue;
}
while (!corder.empty())corder.pop();//由于多组数据，于是需要清空优先队列
counter = reader - 1, otp = 1;//第一个数肯定要选
for (i = 2;i <= n;i ++){//i 定义在外面，方便判定无解后把数列读完
    if (counter)counter --;
    else {
        if (corder.empty() || corder.top() < 2){//已空或者最大的也不够再移动指针
            otp = -1;//otp 即 output
            break;
        }else {
            otp ++, counter = corder.top() - 2;//修改 counter，答案加一
            corder.pop();
        }
    }
    corder.push(reader);//把下一个数推入
}
while (i <= n){//这是用来在无解后读完剩余数字的
    reader.scan();
    i ++;
}
printf("%d\n", otp);

起股 & 中股 & 后股

完整代码如下：

#include <queue>
#include <cstdio>
using std::priority_queue;

const int N = 2e6 + 7;
int n, T, counter, otp;
struct readers{//快读
    char now;
    bool state;
    inline int scan(){
        register int ans = 0;
        state = false;
        while (now = getchar(), 48 > now || now > 57)state = now == 45;
        while (48 <= now && now <= 57){
            ans = (ans<<1) + (ans<<3) + (now^48);
            now = getchar();
        }
        if (state)ans = -ans;
        return ans;
    }
    readers operator >>(int &goal){
        goal = scan();
        return *this;
    }
    operator int(){return scan();}
}reader;
priority_queue<int> corder;

//%: define FLE "logic"
int main(){
//  freopen(FLE ".in", "r", stdin);
//  freopen(FLE ".out", "w", stdout);
    register int i;
    reader>>T;
    while (T --){
        if (reader>>n, n == 1){
            printf(/*"n = 1, "*/ "%d\n", reader?0:-1);
            continue;
        }
//      printf(">>>n is %d<<<\n", n);
        while (!corder.empty())corder.pop();
        counter = reader - 1, otp = 1;
        for (i = 2;i <= n;i ++){
            if (counter)counter --;
            else {
                if (corder.empty() || corder.top() < 2){
                    otp = -1;
//                  printf(">>>break with i = %d<<<\n", i);
                    break;
                }else {
                    otp ++, counter = corder.top() - 2;
                    corder.pop();
                }
            }
//          printf(">>>end with i = %d<<<\n", i);
            corder.push(reader);
        }
        while (i <= n){
            reader.scan();
            i ++;
        }
        printf("%d\n", otp);
    }
    return 0;
}

束股

这道题难度实际上不大，主要是题面有毒。

顺带一提，被 T 的考虑开快读，因为：