#C240130B. 刷野II

标签（Label）

• 思维

网址（Website）

$\qquad$题目详情 - 刷野II - Super

$\qquad$题解 - 刷野II - Super

题解（Solution）

$\qquad$策略：每次找目前还没有打过的且生命值最大的怪去打。

$\qquad$如果当前不去打生命值最大的怪，那么在魔力消耗后再去打就一定会消耗更多的魔力，因此找出每个点对于左边的的最大值和右边的最大值进行比较，先一路过去干掉生命值最大的一定更优。

代码（Code）

#include<bits/stdc++.h>
#include<deque>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5012345;
int n,maxx=0,st,tid,a[N];

int l[N],r[N];
vector<int> gr;
void Solve(){
	maxx=0;For(i,1,n) if(maxx<a[i]) maxx=a[i],st=i;
	maxx=0;For(i,1,st-1) maxx=max(maxx,a[i]),l[i]=maxx,maxx++;
	maxx=0;Rof(i,n,st+1) maxx=max(maxx,a[i]),r[i]=maxx,maxx++;
	{
		int ll=st-1,rr=st+1,sum=a[st],u=a[st]-1;
		gr.emplace_back(st);
		while(ll>0 || rr<=n){
			if(rr>n || l[ll]>=r[rr]){
				if(u>=l[ll]) u--;
				else sum+=(l[ll]-u),u=l[ll]-1;
				gr.emplace_back(ll),
				ll--;
			}else{
				if(u>=r[rr]) u--;
				else sum+=(r[rr]-u),u=r[rr]-1;
				gr.emplace_back(rr),
				rr++;
			}
		}cout<<sum<<'\n';
		for(auto x:gr) cout<<x<<' ';cout<<'\n';
	}
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("lightning");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>tid>>n;For(i,1,n) a[i]=input();
	int Tim=clock();
	Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}