【国庆培训】Fight
文章图片
文章图片
文章图片
#include
#include
#include
#include
#include
#include
using namespace std;
bool vis[3000+100];
struct cir
{
int A,D,H;
int num;
}player[3000+100];
int ak,n;
long long ans;
bool cmp(cir a,cir b)
{
return (a.A*b.num)>(b.A*a.num);
}
int sum;
void read()
{
cin>>n>>ak;
for(int i=1;
i<=n;
++i)
{
cin>>player[i].A>>player[i].D>>player[i].H;
sum+=player[i].A;
player[i].num=ceil(double(player[i].H)/(ak-player[i].D));
}}
int main()
{
freopen("fight.in","r",stdin);
freopen("fight.out","w",stdout);
read();
sort(player+1,player+1+n,cmp);
for(int i=1;
i<=n;
++i)
{
ans+=player[i].num*sum;
sum-=player[i].A;
}
cout 上面的代码是满分代码，该题正解即贪心，我们用num记录杀死一个怪物的所需要攻击的次数，对于任意两个怪物a和b，按照a的攻击力x杀死b所需次数>b的攻击力x杀死a所需次数排序，依次击杀即可。
下面是我最开始写的错的代码，只有20分
#include
#include
#include
#include
#include
#include
using namespace std;
bool vis[3000+100];
struct cir
{
int A,D,H;
int num;
}player[3000+100];
int ak,n;
int ans;
int cnt;
int fr=99999999;
int sum;
void read()
{
cin>>n>>ak;
for(int i=1;
i<=n;
++i)
{
cin>>player[i].A>>player[i].D>>player[i].H;
sum+=player[i].A;
player[i].num=ceil((double)player[i].H/(ak-player[i].D));
ans+=player[i].num*player[i].A;
}
cout 上面错误代码的大致思想是：
【【国庆培训】Fight】我们击杀怪物存在一个基础伤害，就是承受伤害的下限，比如一个怪的攻击为5，击杀他需要4次，还有一个怪攻击为3，击杀他需要2次，那我们定义的基础伤害就是26(4*5+3*2)。然后我们承受的伤害除了基础伤害外就是额外伤害（所谓额外伤害就是我在攻击一个怪物时，除了攻击的怪物以外的其他活着的怪物群殴我造成的伤害），所以我们要使额外伤害最小。
我错误的认为每次都枚举活着的怪物，攻击内个会给我带来最小额外伤害的怪物，直至杀死所有的。但这样就出现了错误，我每一次选取当前造成额外伤害最小的怪，并不一定会确保整体最小，又可能会使以后的额外伤害增大，得不偿失。
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长