打酱油(贪心)1560
时间: 2023-07-10 16:33:43 浏览: 52
这道题是一道典型的贪心算法题目。
题目描述:有一个容量为 n 的油桶,每卖一瓶酱油就能得到一块钱,每卖出一瓶酱油后,油桶的容量就会减少 1。现在有m瓶酱油,每瓶需要占用 ai 的容量,问最多能得到多少钱。
算法思路:首先,需要将酱油按照占用容量从小到大排序。然后,从第一瓶酱油开始卖,每次卖出一瓶酱油后,将当前油桶的容量减去该瓶酱油所占用的容量。如果当前油桶的容量小于 0,则说明无法再卖出酱油,此时需要结束卖酱油的过程。最后,将卖出的酱油数量乘以单价即为最终的收益。
具体实现方式如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100000
int cmp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
int a[MAX_N];
for (int i = 0; i < m; i++) {
scanf("%d", &a[i]);
}
qsort(a, m, sizeof(int), cmp);
int ans = 0, cur = n;
for (int i = 0; i < m && cur > 0; i++) {
if (cur >= a[i]) {
ans++;
cur -= a[i];
}
}
printf("%d\n", ans);
return 0;
}
```
在这个例子中,首先读入 n 和 m,分别表示油桶的容量和酱油的数量。然后,使用一个数组 a 存储每瓶酱油所占用的容量,并按照占用容量从小到大排序。接下来,使用一个循环卖出酱油,每次卖出一瓶酱油后,将当前油桶的容量减去该瓶酱油所占用的容量。如果当前油桶的容量小于 0,则说明无法再卖出酱油,此时需要结束卖酱油的过程。最后,将卖出的酱油数量乘以单价即为最终的收益。
需要注意的是,使用 qsort 函数对数组 a 进行排序时,需要传入一个比较函数 cmp,用来指定排序的方式。在比较函数中,需要将两个元素进行比较,并返回一个整数,表示它们之间的大小关系。在这个例子中,比较函数的实现方式为返回 a - b 的值,表示将 a 放在 b 的前面。