列表

详情

NC222761. MonsterHunter

描述

Ema is the best carry player in a game. In the game, she needs to eliminate monsters. The i-th monster has h_i health points (HP) at the beginning. When a monster is attacked by Ema, its HP is reduced by her attack power. When the HP of a monster is less than or equal to 0, the monster is eliminated.

To make the game more interesting, the attack power is not a constant number. There is a basic attack sequence , and the damage caused is generated by repeating this sequence. Formally, let r_i be the damage caused by the -th attack, we have

To eliminate the monsters as soon as possible, Ema wants to minimize the number of attacks. Can you tell her the minimum number of attacks required to eliminate all the monsters?

输入描述

There are multiple test cases. The first line of the input contains an integer  indicating the number of test cases. For each test case:
The first line contains an integer  () indicating the length of the basic attack sequence.
The second line contains  integers  () indicating the basic attack sequence.
The third line contains an integer  () indicating the number of monsters.
The fourth line contains  integers  () where h_i indicates the initial HP of the -th monster.
It's guaranteed that neither the sum of n nor the sum of m of all test cases will exceed .

输出描述

For each test case output one line containing one integer indicating the minimum number of attacks to eliminate all the monsters.

示例1

输入: 

2
2
3 2
3
2 4 2
5
1 2 3 2 1
2
3 3

输出: 

4
3

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 86ms, 内存消耗: 2780K, 提交时间: 2021-06-15 00:41:21 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int T,n,m;
ll l,r,sum;
int a[100050];
int h[100050];
int f[100050];
ll s[4];
ll t[100050][4];
bool check(ll u)
{
	memset(s,0,sizeof(s));
	memcpy(f,h,sizeof(f));
	for(int i=1;i<=3;++i)
		s[i]=u/n*t[n][i]+t[u%n][i];
	for(int i=1;i<=m;++i)
	{
		int tmp=min((ll)f[i]/3,s[3]);
		if(tmp==0)	continue;
		if((f[i]-tmp*3)&1)	tmp--;
		s[3]-=tmp;	f[i]-=tmp*3;
	}
	for(int i=1;i<=m;++i)
	{
		int tmp=min((ll)f[i]/3,s[3]);
		s[3]-=tmp;	f[i]-=tmp*3;
	}
	s[2]+=s[3];
	for(int i=1;i<=m;++i)
	{
		int tmp=min((ll)f[i]/2,s[2]);
		s[2]-=tmp;	f[i]-=tmp*2;
	}
	s[1]+=s[2];
	ll tmp=0;
	for(int i=1;i<=m;++i)	tmp+=f[i];
	for(int i=1;i<=m;++i)
	{
		int tmp=min((ll)f[i],s[1]);
		s[1]-=tmp;	f[i]-=tmp;
		if(f[i])	return false;
	}
	return true;
}
void calc()
{
	sum=0;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)	scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=3;++j)
			t[i][j]=t[i-1][j];
		t[i][a[i]]++;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;++i)	scanf("%d",&h[i]);
	for(int i=1;i<=m;++i)	sum+=h[i];
	sort(h+1,h+m+1);
	l=0,r=sum;
	while(l<r)
	{
		ll mid=(l+r)>>1;
		if(check(mid))	r=mid;
		else	l=mid+1;
	}
	printf("%lld\n",l);
}
int main()
{
	scanf("%d",&T);
	while(T--)	calc();
	return 0;
}

上一题

© 2024 nowcoder.com