LOADING STUFF...
百度&必应权4, 日IP8000. 查看详情
自助收录

2023年华为OD机考真题:云短信平台优惠活动

算法刷题1年前 (2023)更新 江南白衣
541 0 0
2023年华为OD机考真题:云短信平台优惠活动

全网最全面的华为OD机试真题汇总,100%原题题库,不需要开会员即可查看全部内容,更多考题请查看真题库。

真题库:https://www.yuque.com/codernav.com/od

题目:云短信平台优惠活动
知识点哈希表队列数组统计贪心
时间限制:1s 空间限制:256MB 限定语言:不限
题目描述:
某云短信厂商,为庆祝国庆,推出充值优惠活动。
现在给出客户预算,和优惠售价序列,求最多可获得的短信总条数。
输入描述:
第一行客户预算M,其中 0<=M<=1000000
第二行给出售价表,P1,P2…Pn, 其中 1<=n<=100,Pi为充值i元获得的短信条数。 1<=Pi<=1000, 1<=n<=100
输出描述:
最多获得的短信条数
示例1
输入:
6
10 20 30 40 60
输出:
70
说明:
分两次充值最优,1元、5元各充一次。总条数 10+60=70
示例2
输入:
15
10 20 30 40 60 60 70 80 90 150
输出:
210
说明:
分两次充值最优,10元、5元各充一次。总条数 150+60=210
解题思路:
通过回溯将所有充值的情形模拟一遍,求出其中最大的短信条数
博主使用的是M中取N个数的算法(可以套用到很多题目上),大家也可以使用其他的方法。

代码实现一:

package com.codernav.demo.hwod.exam;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @title 云短信平台优惠活动
 * @Description 某云短信厂商,为庆祝国庆,推出充值优惠活动。
 * 现在给出客户预算,和优惠售价序列,求最多可获得的短信总条数。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static int max = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        sc.nextLine();
        String[] P = sc.nextLine().split(" ");
        combine(P, M, new ArrayList<>(), 0);
        System.out.println(max);
    }

    /**
     * M中取N个数的算法
     *
     * @param strings 出售价表
     * @param n       剩余的预算
     * @param list    充值获得的短信条数的集合
     * @param index   出售价表的索引
     */
    public static void combine(String[] strings, int n, List<Integer> list, int index) {
        if (n == 0) {     //当预算等于0,退出循环
            int count = 0;
            for (Integer integer : list) {
                count += integer;
            }
            max = Math.max(max, count);
        } else {
            for (int i = index; i < strings.length; i++) {
                int x = Integer.parseInt(strings[i]);
                list.add(x);
                combine(strings, n - (i + 1), list, i + 1);
                list.remove(list.size() - 1);
            }
        }
    }
}

代码实现二:Java代码满分实现

package com.codernav.demo.hwod.exam;

import java.util.*;

/**
 * @title 云短信平台优惠活动
 * @Description 某云短信厂商,为庆祝国庆,推出充值优惠活动。
 * 现在给出客户预算,和优惠售价序列,求最多可获得的短信总条数。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        in.nextLine();
        String[] P = in.nextLine().split(" ");
        int[] nums = Arrays.stream(P).mapToInt(Integer::parseInt).toArray();
        System.out.println(buy( nums, m, new HashMap<>()));
    }

    private static int buy(int[] arr, int m, Map<Integer, Integer> cache) {
        if (cache.containsKey(m)) {
            return cache.get(m);
        }
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i+1 > m) {
                break;
            }
            ans = Math.max(ans, arr[i] + buy(arr, m - i - 1, cache));
        }
        cache.put(m, ans);
        return ans;
    }
}

 

© 版权声明

相关文章

暂无评论

暂无评论...