Mint工作室出品
有一只老鼠很喜欢奶酪，但是奶酪被分别放在N个房间里，而且这些房间都有一只猫咪看守，现在它准备和猫咪们做个交易。它有M磅的猫食，想用这M磅猫食换取奶酪。在猫咪看守的每一个房间里有奶酪J[i]磅，同时猫咪需要F[i]磅的食物，如果老鼠给猫咪F[i]×a%的猫食，那么它就可以得到J[i]×a%的奶酪。现在已知每只猫咪对猫食的需求量和每个房间的奶酪数，那老鼠怎样才能换得最多的奶酪呢？
第一行输入两个正整数M和N（M和N不大于10000），后面跟N行（每个房间的奶酪数和猫食的需求量）。
样例1输入
我要评论5 3
7 2
4 3
5 2
样例1输出
13.333
样例2输入
20 3
25 18
24 15
15 10
样例2输出
31.500
首先定义及头文件没有问题：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 10005
double ans;
struct room {//用结构体把两个数据j,f捆在一起
double j, f;
}a[MAXN];
接下来就是我们sort里的cmp函数：
bool cmp(room x, room y) {
if (x.j * y.f > y.j * x.f) return 1;
return 0;
}
你发现了吗？这里我们没有用 x.j / x.f 与 y.j / y.f 比较，而是x.j × y.f 比较 y.j × x.f，乍一看好像并没有什么优势，但是你想，如果是整型的话，还要强制×0.1转换为浮点型，不是麻烦多了吗？（我真厉害）
当我沉浸在似乎发现真理的欣喜中无法自拔时，旁边的大佬来了一句：
那我再不写博客了，哼
噢，他说的应该是对的
最后是主函数部分：
int main() {
std::ios::sync_with_stdio(false);
int n, m;
cin >> m >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i].j >> a[i].f;
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n and m > 0; i ++) {
if (m < a[i].f)
ans += a[i].j * m / a[i].f;
else
ans += a[i].j;
m -= a[i].f;
}
printf("%.3lf", ans);
return 0;
}
完整代码也就是：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 10005
double ans;
struct room {
double j, f;
}a[MAXN];
bool cmp(room x, room y) {
if (x.j * y.f > y.j * x.f) return 1;
return 0;
}
int main() {
std::ios::sync_with_stdio(false);
int n, m;
cin >> m >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i].j >> a[i].f;
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n and m > 0; i ++) {
if (m < a[i].f)
ans += a[i].j * m / a[i].f;
else
ans += a[i].j;
m -= a[i].f;
}
printf("%.3lf", ans);
return 0;
}
所以，我们的Mint水题解第一篇施工完毕！
我知道没有人会点赞的(T_T)
本文地址：https://blog.csdn.net/weixin_46340904/article/details/107180200
如对本文有疑问， 点击进行留言回复！！
H - Antenna Placement POJ - 3020（最小边覆盖）
Unity组件【Camera && Flare Layer】
K - Treasure Exploration POJ - 2594
网友评论