D : Fight with Monsters
题目大意 :
有一组数,每个值对应着一个怪物的 hp 值，现在有两个人，一个自己一个对手,每个人有一个攻击值,
两个人轮流攻击怪物,如果是自己将怪物先打倒,则 + 1 分,反之则不加,在攻击过程中,自己可以使用
特权,轮到对手的时候自己攻击将怪物打倒,从而使得自己能够加分，特权是有限制的,用完特权后剩下的就只
能听天由命了,问在这种情况下自己最多可以得到多少分 ？
析题得说 :
我们知道,两个人是轮流进行的,所以我们通过看能进行几轮,最后该自己的时候怪物还剩下多少 hp 值,
如果说剩下的 hp 值我直接就能干死,说明我们不需要使用特权就能 + 1,相反看一下能够使用几次特权
才能将怪物干掉,因为每个数的顺序是不一样的,我们不知道哪个数对应的特权是几次,但是我们知道特权
使用的次数越少,我们就能得到更高的分,比如一个数需要使用一次特权，一个需要使用两次,那我们肯定
先处理哪个一次特权的数,所以我们可以将所有怪物需要干掉所使用的特权排个序,，然后最后累加处理
即可。
求每个怪物被干掉所需要的特权次数 ？
我是通过 特判 + 循环去模拟,数据多了显然一个一个循环处理肯定会超时,果不其然,在第42个样例的时候就超时
了，然后各种缩减，还是超时,不行了,所以看了一下大佬的,才发现自己是真的菜,没有转过弯将循环算去弄成一个
式子进行处理,这样就铁定不会超时了.
我们最后求的是特权,实际上就是需要多少次 自己的攻击值可以干掉怪物,那直接除一下不就知道需要几次了,但是
这里的时候由于前面都是一对一对,到这里的时候还包括我不用使用特权,也可以干掉 a 点 hp 值,所以这里就需要
我们 (取余得到的结果 / a ) 向上取整 - 1 就是所需要的特权了,另外 余数 = 0 的时候我们需要特殊处理,因
为这里并不是自己能够加分,所以我们可以向前轮回一圈,使得余数是 a + b，然后看需要几次特权处理,与余数不是
0 的道理类似。
为什么向上取整而不是向下取整 ？
看一下第一个样例 :
6 2 3 3
7 10 50 12 1 8
a = 2,b = 3
如果我们最后对 a + b 取余得到的是 4,我们向下取整 4 / 2 = 2,因为还包含一个自己,所以还需要 - 1
但是如果取余得到的 3 ,向下取整 3 / 2 = 1，同样也包含一个自己, 也需要 - 1，这时候答案是 0,但实际
上使用特权的次数 是 1,所以向下取整不可取.
我们试一下向上取整, 3 / 2 向上取整 得到的 是 2, - 1 得到是 1,合适。
Code ：
先看一下我的循环模拟吧,哈哈,思路大体一样,主要是处理特权次数的方式不同。
#include <map>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 2e5 + 10;
int mon[maxn];
map<int,int>cnt;
map<int,int>::iterator it;
int n,a,b,k;
int res = 0;
int main(void) {
scanf("%d%d%d%d",&n,&a,&b,&k);
res = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d",&mon[i]);
int count = 0;
if(mon[i] <= a) res ++; // 本身就 <= a ，可以直接干掉
else {
int m = a + b;
int MOD = mon[i] % m;
if(MOD <= a && MOD != 0) { // 下一个就是自己出手,也可以直接干掉
res ++;
} else if(MOD != 0 && k != 0) { // 余数不为 0 的时候
int ans = a;
while(MOD > ans) { // 模拟,哈哈,可以直接计算的
ans = ans + a;
count ++;
}
if(count == 1) {
k --;
res ++;
continue;
}
if(count > k) continue;
cnt[count] ++;
} else if(MOD == 0 && k != 0) {
int ans = 0;
count = 0;
while(a * ans < b) { // 同上
count ++;
ans ++;
}
if(count == 1) {
k --;
res ++;
continue;
}
if(count > k) continue;
cnt[count] ++;
}
}
}
for(it = cnt.begin(); it != cnt.end(); it ++) { // 最后的处理
int size = k / it->first;
if(size >= it -> second) {
res += it -> second;
k -= it->second;
} else {
res += size;
break;
}
}
printf("%d\n",res);
return 0;
}
贪心代码:
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn],cnt[maxn];
int n,x,b,k;
int main(void) {
scanf("%d%d%d%d",&n,&x,&b,&k);
int MOD = x + b;
for(int i = 1; i <= n; i ++ ){
scanf("%d",&a[i]);
a[i] = a[i] % MOD;
if(a[i] == 0) a[i] += x + b;
a[i] = (a[i] + x - 1) / x - 1; // 向上取整,减 1 是因为本来就该自己了,减去本身
}
sort(a + 1,a + 1 + n);
int res = 0;
for(int i = 1; i <= n; i ++) {
if(a[i] == 0) ++ res;
else if(a[i] <= k) {
++ res;
k -= a[i];
} else {
break;
}
}
cout << res << endl;
return 0;
}
通过这道题,Get 那些干货 ？
1、贪心就是找到其根本,想的东西全面一点,然后尝试着去看能不能推翻现有的结论。
2、能通过一个式子进行计算的就最后不要去模拟,寻找更有效的方法,还是抓其本质。
3、向上取整 : (a + b - 1) / b （减 - 是为了避免整除出现的问题）
向下取整 ： a / b
四舍五入 :（a + b / 2）/ b
注意 ： 负数可不一样哦
⌊59/60⌋=0
⌈59/60⌉=1
⌊-59/60⌋=-1
⌈-59/60⌉=0