贪心算法练习

便利店

题目描述

天宝来到便利店想买些饮料。便利店有各种型号的瓶装饮料售卖,不同型号的饮料卖不同的价格。1瓶0.25升的卖A元,1瓶0.5升的饮料卖B元,1瓶1升的卖C元,1瓶2升的卖D元。便利店里每种饮料都是无限供应。

天宝要买N升的饮料,最少需要花多少钱呢?聪明的你写个程序帮她算算吧。

已知 

1)  1≤A,B,C,D≤10,1≤N≤109   

2)   输入的数据都是整数 

输入

输入数据按照下面格式

A B C D

N

输出

输出天宝要买N升的饮料所需要花的钱最小值。

样例输入 

20 30 70 90
3

样例输出

150

提示

买1瓶2升的饮料和2瓶0.5升的饮料。 这样正好可以买到3升饮料,花费是 90+30+30=150 元。

题解:

最简单的一个,将价格分成两个部分,分别得到一升的最低价格,然后得到两升的最低价格(因为两升的饮料可以直接买两升,也可以买两个1升),然后用总升数N整除2乘按两升买的最低价格,然后N再对2求余数乘只能按1升买的价格。

一定要把所有的数换成long long类型,否则会造成溢出

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    long long a, b, c, d, n;
    cin >> a >> b >> c >> d;
    cin >> n;
    long long min1 = min(min(a * 4, b * 2), c);
    long long min2 = min(min1 * 2, d);
    cout << n / 2 * min2 + n % 2 * min1 << endl;
}

删数问题

给定一个十进制正整数 n(0<n<1000000000),每个数位上数字均不为 00。n 的位数为 m
现在从 m 位中删除 k 位(0<k<m),求生成的新整数最小为多少?
例如: n=9128456,k=2, 则生成的新整数最小为 12456。

输入格式

第一行 t, 表示有 t 组数据;
接下来 t 行,每一行表示一组测试数据,每组测试数据包含两个数字 n,k

输出格式

t 行,每行一个数字,表示从 n 中删除 k 位后得到的最小整数。

输出时每行末尾的多余空格,不影响答案正确性

样例输入

2
9128456 2
1444 3

样例输出

12456
1

题解:

方法是如果一个数大于他后边的数,那么就把他删除掉。因为要生成最小的整数,就一定要删除最靠前的而且比较大的那一个。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int k;
        string s;
        cin >> s >> k;
        while (k--)
        {
            
            for (long unsigned int i = 0; i < s.size(); i++)
            {
                if (s[i] > s[i + 1])
                {
                    s.erase(s.begin() + i);
                    i--;
                    break;
                }
            }
        }
        cout << s << endl;
    }

    return 0;
}
除特殊声明外,本站所有内容谢绝转载。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇