[Codeforces 1141E] Superhero Battle

[Codeforces 1141E] Superhero Battle

Problem - E - Codeforces

문제 설명 : 

몬스터의 체력과 n명의 플레이어의 공격력이 각각 주어진다. 각 플레이어들은 1번부터 순서대로 몬스터를 공격해서 본인의 공격력만큼 몬스터의 체력을 변화시킬 수 있다(공격력이 음수면 체력을 깎고지만, 양수면 힐을 해준다). 마지막 플레이어까지 모두 공격을 마쳤으면 다시 1번 째 플레이어로 돌아와서 이를 반복한다. 이렇게 해서 몬스터의 체력이 0이하로 만들 수 있는지와, 가능하다면 그 시점은 몇 번째인지를 구하는 문제이다.

 

풀이 : 

H의 최대가 10^12(1조)이기 때문에 직접 0이 될 때까지 돌려보는 것은 불가능하다. 플레이어들이 모두 한번씩 공격을 하는데 그 중에서 어느 시점이 몬스터의 체력을 가장 많이 깎는 지가 중요하다. 예를 들어서 -1 -2 -3 +5 와 같은 데이터가 있다고 하자(H,N 생략). 3번 째 플레이어까지는 값이 음수이니 괴물의 체력을 깎지만 4번 째는 양수이므로 다시 체력을 회복시키는 셈이다. 따라서 각 턴에서 몬스터의 체력을 가장 많이 깎은 시점은 3번 째 플레이어가 공격을 한 직후가 되는 것이다. 이와 같이 어느 시점에서 체력을 가장 많이 깎는 지를 알아내기 위해서는 누적합 배열이 필요하다. 누적합 배열의 값들 중에서 가장 값이 작은 인덱스가 바로 그 시점이 되는 것이다. 그 시점을 알아냈다면 몇 바퀴를 돌아야 그 시점에서 체력을 0으로 깎을 수 있는지를 계산헤야 한다. 이는 H를 모든 플레이어들의 공격력의 합('사이클'이라고 표현하겠다)으로 나누면 총 몇 바퀴를 돌아야하는지 알 수 있다.

 

주의할 점 : 

상황에 따라서 절대로 몬스터의 체력을 0이하로 만들 수 없는 경우가 존재한다. 바로 플레이어들의 공격력 누적합이 모두 양수일 경우이다. 하지만 사이클은 양수라 하더라도 도중에 누적합이 0보다 작아지는 경우가 존재할 수 있으므로 이는 다시 예외처리를 해야한다.(예 : -1 , +2)

 

배운 점 : 

-

 

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
// #define SIZE
// #define IMP
// #define INF
// const int MOD=
struct S{
	int a,b;

	S(){}
	S(int _a,int _b){
		a=_a;
		b=_b;
	}

	const bool operator<(const S &o) const{
		return a<o.a;
	}
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
const int SIZE= 200009;


ll arr[SIZE],psum[SIZE];
int main(){
	ll H,n;	scanf("%lld %lld",&H,&n);

	ll min_val=1<<30;
	for(int i=1 ; i<=n ; i++){
		scanf("%lld\n",&arr[i]);
		psum[i]=psum[i-1]+arr[i];
		if(-psum[i]>=H){
			printf("%d\n",i);
			return 0;
		}
		min_val=min(min_val,psum[i]);
	}
	ll cycle=psum[n];
	if(cycle>=0){
		printf("-1\n");
		return 0;
	}

	ll diff=H+min_val;
	ll q=diff/(-cycle);
	if(diff%-cycle) q++;
	ll r=H-q*-cycle;

	ll ans=q*n;
	for(int i=1 ; i<=n ; i++){
		ans++;
		if(-psum[i]>=r){
			break;
		}
	}

	printf("%lld\n",ans);
	return 0;
}