P10073题解

· · 题解

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

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