6783. Discount

HDOJ 6783. Discount

2020 年百度之星·程序设计大赛 - 初赛三

• 6783. Discount
• 6784. Game
• 6785. Permutation
• 6786. Intersection

题目：6783. Discount

问题描述：

学皇来到了一个餐馆吃饭。他觉得这家餐馆很好吃，于是就想办个会员。

一共有 n 种会员充值卡套餐，假设学皇这餐饭的消费为 a 元，选择第 i 种套餐，需要充值 b[i]∗a 的钱，这次吃饭可以打 c[i]×10 折，由充值的钱支付（即这次吃饭只需要从充值金额中扣除 a×c[i] 元）。以后用剩余的充值的钱吃饭不再打折。

请问学皇应该选择哪个套餐（必须选择恰好一个套餐），使得优惠的比例最大？

优惠比例的定义是把充的钱用完以后，(本来应该付的钱 - 实际付的钱) / 本来应该付的钱。在这个题目里，实际付的钱就是这次充值的花费。

输入：

第一行一个整数 test(1≤test≤100) 表示数据组数。
对于每组数据，第一行一个正整数 n(1≤n≤100) 表示套餐的数目。
接下来 n 行，每行一个正整数 bi 和一个小数 c[i](0≤c[i]≤1，c[i] 最多包含两位小数)。

输出：

对于每组数据，输出一个五位小数表示最大的优惠比例。如果小数点后超过五位，四舍五入到五位。

样本输入：

1
2
2 0.5
3 0.1

样本输出：

0.23077

样例解释：

对于第一种套餐，优惠比例为 0.5a / (2a + 0.5a） = 0.2；

对于第二种套餐，优惠比例为 0.9a / (3a + 0.9a） = 9 / 39；

方法：模拟

思路：根据题目给出的公式进行计算即可。题中给出优惠比例的计算公式为(本来应该付的钱 - 实际付的钱) / 本来应该付的钱 ，根据题意得出具体公式为(b[i] * a + (1 - c[i]) * a - b[i] * a) / b[i] * a + (1 - c[i]) * a (其中b[i] * a + (1 - c[i]) * a为本来应该付的钱，b[i] * a为实际付的钱)，化简后即为1 - c[i] / b[i] + (1 - c[i])。

运行数据：执行用时：343MS，内存消耗：14220K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int test = sc.nextInt();

        while (test-- > 0) {
            int n = sc.nextInt();
            double result = 0;
            while (n-- > 0) {
                int b = sc.nextInt();
                double c = 1 - sc.nextDouble();
                result = Math.max(result, Math.round(c / (b + c) * 100000) / (double)100000);
            }
            System.out.println(String.format("%.5f", result));
        }
    }
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！