给出Codeoforces题目10E Greedy Change的Ruby代码
时间: 2023-02-10 20:02:35 浏览: 69
这里是 CodeForces 题目 10E Greedy Change 的 Ruby 代码:
```
# frozen_string_literal: true
def main
n, k, _ = gets.split.map(&:to_i)
coins = gets.split.map(&:to_i).sort.reverse
ans = 0
coins.each do |coin|
ans += k / coin
k %= coin
end
puts ans
end
main
```
代码的思跑是:从大到小枚举硬币的面值,每次尽可能多地用这种硬币。直到无法再使用这种硬币为止。
相关问题
给出Codeoforces题目10E Greedy Change的C++代码
我可以为您提供一个 C 语言的代码示例,您可以参考它,完成这道 Codeoforces 的题目 10E Greedy Change。
请注意,这仅是一个示例代码,并不一定是最优解。
```
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000000
int n, m, a[MAXN+5];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = n; i >= 1; i--) {
if (m >= a[i]) {
printf("%d ", m / a[i]);
m %= a[i];
} else {
printf("0 ");
}
}
printf("\n");
return 0;
}
```
这道题的解题思路是:贪心策略。
具体来说,对于给定的数组 `a` 和数字 `m`,从后往前枚举数组中的每一个数字,若 `m` 大于等于当前数字,则输出 `m` 除以当前数字的商,然后用 `m` 取余当前数字的余数。若 `m` 小于当前数字,则输出 0。
最后,记得要在程序结束时输出换行符。
希望这份代码能帮助到您。
给出Codeoforces题目10E Greedy Change的C代码
### 回答1:
下面是Codeoforces上题目10E Greedy Change的C代码:
```
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
const int N=5050, M=25, INF=0x3f3f3f3f;
int n, m, ans, minv[M], p[M], vis[M];
int head[N], dis[N], tot=1;
struct node
{
int to, next, w;
} e[N<<1];
inline void add(int u, int v, int w)
{
e[++tot]=(node){v, head[u], w};
head[u]=tot;
}
inline void spfa()
{
queue<int> q;
memset(dis, 0x3f, sizeof(dis));
dis[0]=0, vis[0]=1, q.push(0);
while(!q.empty())
{
int u=q.front(); q.pop();
vis[u]=0;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
if(!vis[v]) vis[v]=1, q.push(v);
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<=m; i++) scanf("%d%d", &p[i], &minv[i]);
for(int i=1; i<=m; i++)
for(int j=minv[i]; j<=n; j++)
add(j-minv[i], j, p[i]);
spfa();
printf("%d\n", dis[n]);
return 0;
}
```
这道题是一道最短路题目,使用spfa算法求解。题目要求我们用最少的钱数买到价值为n的物品,我们可以将每种物品看作一条边,价值为边权,价格为边的费用。我们从0开始建图,对于每一种物品,都从它的最小价值开始连向它的价值的所有整数倍
### 回答2:
下面是题目10E Greedy Change的C代码:
```c
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
// 创建一个数组存储每一个硬币面值
int coins[] = {1, 2, 5, 10, 20, 50, 100, 200};
// 创建一个变量保存最小硬币数
int minCoins = 0;
// 从最大面值硬币开始,逐个进行贪心选择
for (int i = sizeof(coins) / sizeof(coins[0]) - 1; i >= 0; i--) {
// 当前面值硬币最多能用几枚
int numCoins = n / coins[i];
// 更新总硬币数
minCoins += numCoins;
// 更新剩余金额
n -= numCoins * coins[i];
// 如果已达到目标金额,跳出循环
if (n == 0) {
break;
}
}
printf("%d\n", minCoins);
return 0;
}
```
该代码按照贪心算法的思想,从最大面值的硬币开始,尽可能多地使用当前面值硬币,直到满足目标金额为止。其中`n`是输入的目标金额,`coins`数组保存硬币的面值,`minCoins`保存最少的硬币数。代码通过循环遍历每个面值硬币,计算当前面值硬币最多能使用的数量,更新总硬币数和剩余金额。然后在每次循环的末尾判断剩余金额是否为0,如果是则跳出循环并输出最小硬币数。最后打印输出最小硬币数`minCoins`。
### 回答3:
下面是Codeforces题目10E Greedy Change的C代码:
```c
#include <stdio.h>
void greedyChange(int n) {
int notes[7] = { 1, 2, 5, 10, 20, 50, 100 };
int count[7] = { 0 };
int i, j;
for (i = 6; i >= 0; i--) {
count[i] = n / notes[i];
n = n % notes[i];
}
for (j = 0; j < 7; j++) {
printf("%d ", count[j]);
}
}
int main() {
int n;
scanf("%d", &n);
greedyChange(n);
return 0;
}
```
以上代码实现了一个贪心算法,用于计算某个整数n的找零方案。题目要求找零的面值有1、2、5、10、20、50和100。代码首先定义一个 `notes` 数组和一个 `count` 数组分别存储面值和对应的数量。然后,使用贪心算法进行计算,从大到小遍历 `notes` 数组,依次计算每个面值的数量,并更新剩余的找零金额。最后,输出每个面值的数量。在 `main` 函数中,从输入中读取n,并调用 `greedyChange` 函数进行计算和输出。