模板
A、小红购物
跳转原题点击此:[A题地址](A-小红购物_牛客周赛 Round 25 (nowcoder.com))
1、题目大意
小红购买了n件物品,但是对其中部分商品不满意要退货,但是退货要收取手续费,手续为为\(max(5, \lfloor {该商品价格 / 100} \rfloor)\),问你小红最终需要支出多少钱。
2、题目解析
普通的模拟题目,对价格按照下标从0开始,这样就与是否退货的字符串(string)对应上了。因为cpp的整数整除是向下整除的,所以无需过多操作。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
int n;
int f[N];
string s;
void solve()
{
cin >> n;
for(int i = 0 ; i < n ; i++)
cin >> f[i];
cin >> s;
ll ans = 0;
for(int i = 0; i < n; i++)
{
if(s[i] == 'F')
ans += max(5, f[i] / 100);
else
ans += f[i];
}
cout << ans << endl;
}
int main()
{
solve();
return 0;
}
B、小红吃桃
跳转原题点击此:B题地址
1、题目大意
小红的n个桃子有甜度和酸度,要求 甜度的乘积 \(+\) 酸度的乘积,其中每个桃子的甜度和酸度可以交换,问你最终的和最大为多少。
2、题目解析
要获得某个乘积最大,只需要这里面最大的数放在一起,就一定能获得最大的乘积和,剩下的较小的数在一起,这样和就是最大。贪心--乘积效应
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int mod = 1e9 + 7;
int n;
ll a[N], b[N];
ll ans1, ans2;
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++)
cin >> b[i];
ans1 = 1, ans2 = 1;
for(int i = 1; i <= n; i++)
{
ans1 = ans1 * min(a[i], b[i]) % mod;
ans2 = ans2 * max(a[i], b[i]) % mod;
}
cout << (ans1 + ans2) % mod << endl;
}
int main()
{
solve();
return 0;
}
C、小红的踏前斩
跳转原题点击此:C题地址
1、题目大意
一共有n个怪物,第\(i\)个怪物的血量为\(a_i\);而小红有两个技能:1、使某个怪物的血量减一,消耗1EXP;2、使第一个怪物血量减一,该怪物后面的第一个怪物血量减二,后面的第二个怪物血量减三,消耗5EXP。当怪物血量小于等于0时为被消灭。问你小红消灭所有怪物的最小EXP。
2、题目解析
注意到,第二个技能以5EXP换的6血量,而第一个技能5EXP只能换5血量。所以我们要尽可能地满足第二个技能条件,所以当满足\(a[i]\ge1、a[i+1]\ge2、a[i+2]\ge3\)时,就可以使用第二个技能;其他条件就是第一个技能。
知道贪心条件,还要确定遍历顺序,先看例子:
\([1, 4, 8, 7, 6]\):从前往后 -> \([0, 2, 4, 7, 6]\) -> \([0, 0, 1, 1, 6]\)
从后往前 -> \([1, 4, 6, 3, 0]\) -> \([1, 3, 4, 0, 0]\) -> \([0, 1, 1, 0, 0]\)
这是因为:从后往前不会影响前面的可能存在的满足第二个技能的血量序列,而从前往后会影响后面满足第二个技能的血量序列,注意区别!!!!。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n;
ll f[N];
ll ans;
void solve()
{
memset(f, 0, sizeof f);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> f[i];
ans = 0;
for(int i = n - 2; i >= 1; i--)
{
if(f[i] >= 1 && f[i + 1] >= 2 && f[i + 2] >= 3)
{
ll tmp = min({f[i], f[i + 1] / 2, f[i + 2] / 3});
ans += 5ll * tmp;
f[i] -= tmp;
f[i + 1] -= tmp * 2;
f[i + 2] -= tmp * 3;
ans += f[i + 2];
f[i + 2] = 0;
}
}
// 最后找到无法满足第二个技能条件的血量,加上即可。
for(int i = 1; i <= n; i++)
ans += f[i];
cout << ans;
}
int main()
{
solve();
return 0;
}