欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

Mint水题解第一篇:老鼠与猫的交易(题解)

程序员文章站 2022-06-22 08:54:27
Mint工作室出品先附上题解#include #include #include #include #include using namespace std;#define MAXN 10005double ans;struct room {double j, f;}a[MAXN];bool cmp(room x, room y)...

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