【2018 CodeM】资格赛---下单

Myth丶恋晨 2022-05-23 00:54 148阅读 0赞

## 前言 ##

这道题目应该算签到题了吧（我大概扫了一下，感觉这道题目应该是最简单的 ^\_^）

注：如果您现在还没有AC，并且比赛还没有结束，我建议再想想，认真再重新读下题目描述，或许你就会发现原来是自己想复杂了（不管你是不是这样的情形，反正我当时是这样的，哈哈）

## 题目描述 ##

**\[编程|1000分\] 下单**

时间限制：C/C++ 1秒，其他语言 2秒  
空间限制：C/C++ 262144K，其他语言 524288K

[题目链接 — 牛客网][Link 1]

**题目描述**

美团在吃喝玩乐等很多方面都给大家提供了便利。最近又增加了一项新业务：小象生鲜。这是新零售超市，你既可以在线下超市门店选购生鲜食品，也可以在手机App上下单，最快30分钟就配送到家。  
新店开张免不了大优惠。我们要在小象生鲜超市里采购n个物品，每个物品价格为ai，有一些物品可以选择八折优惠（称为特价优惠）。  
有m种满减优惠方式，满减优惠方式只有在所有物品都不选择特价优惠时才能使用，且最多只可以选择最多一款。  
每种满减优惠描述为(bi,ci)，即满bi减ci（当消费>=bi时优惠ci）。  
求要买齐这n个物品（必须一单买齐），至少需要多少钱（保留两位小数）。

**输入描述:**

第一行，两个整数n,m。  
接下来n行，每行一个正整数ai，以及一个0/1表示是否可以选择特价优惠（1表示可以）。  
接下来m行，每行两个正整数bi,ci，描述一款满减优惠。

1 <= n,m <=10  
1 <= ai <= 100  
1 <= ci < bi <= 1000

**输出描述:**

一行一个实数，表示至少需要消耗的钱数（保留恰好两位小数）。

**示例1**

输入

2 1
    6 1
    10 1
    12 2

输出

12.80

**示例2**

输入

2 2
    6 1
    10 1
    5 1
    16 6

输出

10.00

## 题目分析 ##

最开始拿到这道题目，读了下题目，题意应该是很容易读懂的，毕竟这样的场景在现实生活中经常出现嘛（感觉这道题目命的很不错呀 ^\_^）

咋一看，我们如何进行选取哪些物品进行优惠？脑袋马上就闪出DP（假装心中一万个DP）。

然后就开始认真做题了（傻了吧唧的）

做了一半，发现这题是真的难（自己太菜就太菜，还怪题目难，哼，就是这么不讲理）

想了下，真的难，难道是我题目理解错误了？（好像开窍了）

好吧，让我们来画重点了。

> 美团在吃喝玩乐等很多方面都给大家提供了便利。最近又增加了一项新业务：小象生鲜。这是新零售超市，你既可以在线下超市门店选购生鲜食品，也可以在手机App上下单，最快30分钟就配送到家。  
> 新店开张免不了大优惠。我们要在小象生鲜超市里采购n个物品，每个物品价格为ai，有一些物品可以选择八折优惠（称为特价优惠）。  
> **有m种满减优惠方式，满减优惠方式只有在所有物品都不选择特价优惠时才能使用，且最多只可以选择最多一款。**  
> 每种满减优惠描述为(bi,ci)，即满bi减ci（当消费>=bi时优惠ci）。  
> 求要买齐这n个物品（**必须一单买齐**），至少需要多少钱（保留两位小数）。

注意我标注的重点，然后再想想应该明白了

**只能使用一种满减，并且只能一单买完**（我就是最开始以为可以使用多种满减方案，发现这道题目是真的难）

## AC代码 ##

#include <bits/stdc++.h>
    using namespace std;
    int a[11][2];
    int bc[11][2];
    int main(){
        int n,m;
        cin>>n>>m;
        for(int i=0;i<n;i++){
            cin>>a[i][0]>>a[i][1];
        }
        for(int i=0;i<m;i++){
            cin>>bc[i][0]>>bc[i][1];
        }
        double res = 0;     //结果
        double temp = 0;       //商品总额
        for(int i=0;i<n;i++){
            temp += a[i][0];
            if(a[i][1]){
                res += a[i][0] * 0.8;
            } else {
                res += a[i][0];
            }
        }
        for(int i=0;i<m;i++){       //遍历选择最优的满减
            if(temp >= bc[i][0]){
                if(temp-bc[i][1] < res){
                    res = temp-bc[i][1];
                }
            }
        }
        cout<<setiosflags(ios::fixed)<<setprecision(2)<<res<<endl;
        return 0;
    }

**注：** 如有错误之处，还望指正，谢谢。欢迎dalao留言评论

[Link 1]: https://www.nowcoder.com/activity/2018codem/oj