问题 E: 便利店

题目描述

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

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

已知

1） 1≤A,B,C,D≤108 ，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 元。

问题分析

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Yl{
    int v; //饮料体积
    int p; //1瓶饮料价格
};

bool cmp(const Yl& a,const Yl& b) {
    return a.v*b.p>b.v*a.p; //这个就是上面推出的排序规则
}

signed main() {
    vector<Yl> a(4);
    a[0].v=250; a[1].v=500; //把升转换为毫升，这样好计算
    a[2].v=1000; a[3].v=2000;
    for(int i=0;i<4;i++) {
        cin>>a[i].p; //输入这4种饮料的价格
    }
    sort(a.begin(),a.end(),cmp); //我们想优先选择体积大又便宜的饮料，岂不美哉！
    int n;
    cin>>n; //需求的饮料体积
    n=n*1000; //记得这里也要转换为毫升
    int ans=0,ps; //ans是最后的钱，ps是每种饮料的需要瓶数
    for(int i=0;i<4 && n>0;i++) { //这里加一个条件，就是如果还没有到n升的话就继续下一个类型饮料
        ps=n/a[i].v; //当前饮料需要几瓶
        n=n-ps*a[i].v; //还需要多少体积
        ans=ans+ps*a[i].p; //当前饮料单价?瓶数
    }
    cout<<ans;
}