滴滴出行2017秋招笔试--餐馆消费问题

问题描述

某餐馆有n张桌子，每张桌子有一个参数：a 可容纳的最大人数； 有m批客人，每批客人有两个参数:b人数，c预计消费金额。 在不允许拼桌的情况下，请实现一个算法选择其中一部分客人，使得总预计消费金额最大。 输入描述: 输入包括m+2行。 第一行两个整数n(1 <= n <= 50000),m(1 <= m <= 50000) 第二行为n个参数a,即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内。 接下来m行，每行两个参数b,c。分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。 输出描述: 输出一个整数,表示最大的总预计消费金额 输入例子: 3 5 2 4 2 1 3 3 5 3 7 5 9 1 10 输出例子: 20

java实现

private static int tableNum; private static int cusNum; private static int[] maximumCapacityOfTables; private static int[][] pepAndMoneyPerTable; public static void main(String[] args) { getInput(); sortOfMaximumCapacityOfTables(); sortOfCustomAndMoney(); System.out.println(match()); } /** * 获取信息输入（m+2行） */ public static void getInput(){ Scanner sc = new Scanner(System.in); System.out.println("请输入桌子数量及顾客批数，用空格隔开："); tableNum=sc.nextInt(); cusNum = sc.nextInt(); sc = new Scanner(System.in); System.out.println("请输入桌子能够容纳客人的数量，用空格隔开："); maximumCapacityOfTables = new int[tableNum]; String[] pepNumInput = sc.nextLine().split("\\s+"); for(int i=0;i<pepNumInput.length;i++){ maximumCapacityOfTables[i]=Integer.valueOf(pepNumInput[i]); } pepAndMoneyPerTable = new int[cusNum][2]; for(int i=0;i<cusNum;i++){ sc = new Scanner(System.in); System.out.println("请输入第"+(i+1)+"批客人的人数及消费总额，用空格隔开："); pepAndMoneyPerTable[i][0]=sc.nextInt(); pepAndMoneyPerTable[i][1]=sc.nextInt(); } } /** * 根据桌子所能容纳的最多人数进行升序排列 */ public static void sortOfMaximumCapacityOfTables(){ for(int i=0;i<tableNum-1;i++){ for(int j=i+1;j<tableNum;j++){ int temp = maximumCapacityOfTables[i]; if(maximumCapacityOfTables[i]>maximumCapacityOfTables[j]){ maximumCapacityOfTables[i]=maximumCapacityOfTables[j]; maximumCapacityOfTables[j]=temp; } } } } /** * 根据每桌的消费金额降序排列，当金额相等时，按照人数升序排列 */ public static void sortOfCustomAndMoney(){ for(int i=0;i<cusNum-1;i++){ for(int j=i+1;j<cusNum;j++){ int[] temp = pepAndMoneyPerTable[i]; boolean moneyNeedSort = pepAndMoneyPerTable[i][1]<pepAndMoneyPerTable[j][1]; boolean peopleNeedSort = (pepAndMoneyPerTable[i][1]==pepAndMoneyPerTable[j][1])&&(pepAndMoneyPerTable[i][0]>pepAndMoneyPerTable[j][0]); if(moneyNeedSort||peopleNeedSort){ pepAndMoneyPerTable[i]=pepAndMoneyPerTable[j]; pepAndMoneyPerTable[j]=temp; } } } } /** * 根据排序后的顾客数量及消费金额与排序后的桌子相匹配 * @return */ public static int match(){ int totalMoney=0; for(int i=0;i<tableNum;i++){ boolean thisTableIsEmpty=true; for(int j=0;j<cusNum;j++){ boolean canSeat=pepAndMoneyPerTable[j][0]<=maximumCapacityOfTables[i]; if(thisTableIsEmpty&&canSeat&&pepAndMoneyPerTable[j][1]>0){ totalMoney+=pepAndMoneyPerTable[j][1]; thisTableIsEmpty=false; //此处的消费金额需要重置，否则每次都会按照最高金额进行相加 pepAndMoneyPerTable[j][1]=0; break; } } } return totalMoney; }