Codeforces Round #547 (Div. 3) E. Superhero Battle (数学)

题意:有一个HP为\(h\)的大怪兽,你需要轮流进行\(i\)次操作.每次可以使\(h+=d_i\)(\(d_i\)有正有负),当第\(n\)次操作完成后,再从第一次开始,问能否使得怪兽的HP变为\(0\)或更低,如果可以,输出操作次数,否则输出\(-1\).
题解:我们首先求\(d\)的前缀和,如果在求的过程中就能使怪兽死掉的话,直接输出即可.然后再去判断\(pre[n]\)是否小于\(0\),如果不小于,那么我们每一个循环得到的都是正的贡献,永远也打不死怪兽!再来看.我们最后的操作次数一定是刚好跑了几个循环,或者跑了几个循环后再从起始位置选了几个,所以我们可以枚举前缀和,每次减去当前前缀和,然后再去求循环次数(除以\(pre[n]\)上取整),更新答案的最小值就好了.

代码:

ll h;

int n;

ll d[N];

ll pre[N];

ll ans=1e18;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>h;

    cin>>n;

    rep(i,1,n){

    	cin>>d[i];

    }

    rep(i,1,n){

    	pre[i]=pre[i-1]+d[i];

    	if(pre[i]<=-h){

    		cout<<i<<'\n';

    		return 0;

    	}

    }

    if(pre[n]>=0) {cout<<-1<<'\n';return 0;}

    pre[n]=-pre[n];

    rep(i,0,n){

    	ll cur=h;

    	cur+=pre[i];

    	ll cnt=(cur-1)/pre[n]+1;

    	ans=min(ans,cnt*n+i);

    }

    cout<<ans<<'\n';

    return 0;

}

巴特西

Codeforces Round #547 (Div. 3) E. Superhero Battle (数学)

最新文章

热门文章