自动搬运

查看原文

来自洛谷，原作者为

	HansLimon 咕噜咕噜

搬运于2025-08-24 22:00:50，当前版本为作者最后更新于2020-07-29 11:09:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

破题 & 承题

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

在给出的数中选一定量的数。对于这之中的一个数 $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 的考虑开快读，因为：