自动搬运

查看原文

来自洛谷，原作者为

	2022tysc0776 **

搬运于2025-08-24 22:54:25，当前版本为作者最后更新于2024-01-21 15:58:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

其实这题比较简单，本人考场上想出来了正解，但是我当时太大意了，忘了输出第二行的答案，然后我又不大自信，所以没有检查，狂挂 100 分

说回题目，我们先猜一个结论：每次都找一个当前除了已经打完的怪物之外，最大血量的怪物 $u$，接一路打过去，这样的走法一定最优。

然后说证明：我们用反证法，如果我们当前不走上面结论的走法，肯定会多走一点才到 $u$，$u$ 是当前除吃完的怪物的最大血量的怪物，所以多走一点肯定不优。

但是还有一个问题，题目不保证所有怪物的血量不同，有没有可能，两个怪物的血量相同但是先走某一个更优呢？

然后再想一下其实也能发现是不可能的，因为这两个怪物肯定都要打，不管先打哪个，最后的所需的 $x$ 肯定是一样的。

那么代码就很好写了：

#include <bits/stdc++.h>
using namespace std;
int n,d,a[5000010],as[5000010],cnt=1;
pair<int,int> b[5000010];
int main(){
	scanf("%d%d",&d,&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i].first=a[i];b[i].second=i;
	}
	sort(b+1,b+n+1);
	int lid=b[n].second,rid=b[n].second,id=n-1;
	int ans=b[n].first,x=b[n].first-1;
	as[1]=b[n].second;
	while(lid!=1||rid!=n){
		if(b[id].second<lid){
			for(int i=lid-1;i>=b[id].second;i--){
				lid=i;
				if(x<a[i]) x=a[i],ans=a[i]+(rid-lid);
				x--;
				as[++cnt]=i;
			}
		}else if(b[id].second>rid){
			for(int i=rid+1;i<=b[id].second;i++){
				rid=i;
				if(x<a[i]) x=a[i],ans=a[i]+(rid-lid);
				x--;
				as[++cnt]=i;
			}
		}
		id--;
	}
	printf("%d\n",ans);
	for(int i=1;i<=cnt;i++) printf("%d ",as[i]); 
	return 0;
}

而且我的想法和别人不太一样，还有这是本人第一次题解，所以如有问题，可在评论区指出。