华为OD真题-- 短信优惠-带答案

逃离我推掉我的手 2023-10-13 15:58 42阅读 0赞

/\*\*

*  题目描述：
 *  某云短信厂商，为庆祝国庆，推出充值优惠活动。
 *  现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数。
 *  输入描述：
 *  第一行客户预算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
 *

\*/

public class MessageDiscounts {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int money = Integer.parseInt(sc.nextLine());
            //性价比
            int[] messageCount = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer ::parseInt).toArray();
            ValueIndex [] valueIndices = new ValueIndex[messageCount.length + 1];
            HashMap<Integer,Integer> hashMap = new HashMap<>();
            //下标从1开始，表示价值
            for (int i = 1; i <= messageCount.length; i++){
                valueIndices[i] = new ValueIndex(i,(double)messageCount[i-1]/i);
                hashMap.put(i,messageCount[i-1]);
            }
            //截取下标从1开始的数组
            valueIndices = Arrays.copyOfRange(valueIndices,1,valueIndices.length);
            //按性价比排序
            Arrays.sort(valueIndices,Comparator.comparingDouble((ValueIndex o1) -> o1.value).reversed());
            //选出最合适的方案
            int allCount = 0;
            for (int j = 0; j < messageCount.length; j++){
                if (money == 0){
                    break;
                }
                if (money >= valueIndices[j].index){
                    money = money - valueIndices[j].index;
                    allCount = allCount + hashMap.get(valueIndices[j].index);
                }
            }
            System.out.println(allCount);
        }
    
       static class  ValueIndex{
            int index;
            double value;
    
            public  ValueIndex(int index, double value) {
                this.index = index;
                this.value = value;
            }
       }
    }