小H和迷宫

72 阅读 0 评论 48 点赞

我是靠谱客的博主香蕉枕头，这篇文章主要介绍小H和迷宫，现在分享给大家，希望可以做个参考。

链接：https://ac.nowcoder.com/acm/problem/15156
来源：牛客网

题目描述

小H陷入了一个迷宫中，迷宫里有一个可怕的怪兽，血量有N点，小H有三瓶魔法药水，分别可以使怪兽损失a%、b%、c%的血量(之后怪兽的血量会向下取整)，小H想合理地运用这三瓶药水，使怪兽失去尽可能多的血量

注意:每瓶药水只能用一次

输入描述:

复制代码

1
一行，四个整数 N,a,b,c

输出描述:

复制代码

1
一行，一个整数w，表示最多能使得怪兽扣减多少血量

示例1

输入

复制代码

1
100 20 15 0

输出

复制代码

1
32

备注:

复制代码

1
5≤N≤109，0≤a,b,c≤100

这里我用的全排列枚举

不然的话比如说这组数据

105 20 25 0

105-(105*0.8+(84为105*0.8后向下取整)84*0.75) = 42

105-(105*0.75(78为105*0.75后向下取整)*0.8)=43

答案是不是不一样?

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <string>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(long long a,long long b){
return a>b;
}
int main(){
long long n,a,b,c;
long long num[10010];
scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
num[0]=a;
num[1]=b;
num[2]=c;
sort(num,num+3,cmp);
long long m=-1;
do{
long long sum=0;
sum=n*(100-num[0])/100;//剩余血量
sum=sum*(100-num[1])/100;
sum=sum*(100-num[2])/100;
sum=n-sum;
m=max(m,sum);
}while(next_permutation(num,num+3));
printf("%lld",m);
return 0;
}