首页 > 代码库 > 滴滴笔试题 就餐问题

滴滴笔试题 就餐问题

题目:餐馆有n张桌子,每张桌子有只能坐固定的人数,现在有批客户每批客户有a人,消费金额是c,请问怎样安排客户,餐馆获利最多

Example:

n张桌子的容纳人数:{2,4,2}

客户批次和消费金额{1,3}、{3,5},{3,7},{5,9},{1,10}

解题思路先把桌子的容纳人数排序,然后对客户进行消费金额的逆序排序,找到桌子最小,有刚好容纳该批客户的桌子

参考代码:

package cn.edu.algorithm.prototype;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner scan = new Scanner(System.in);        while (scan.hasNext()) {            int n = scan.nextInt();            int m = scan.nextInt();            ArrayList<Integer> desk = new ArrayList<Integer>();            for (int i = 0; i < n; i++) {                desk.add(scan.nextInt());            }            Collections.sort(desk);            System.out.println(desk);            ArrayList<Group> customer = new ArrayList<Group>();            for (int i = 0; i < m; i++) {                Group tem = new Group();                tem.setN(scan.nextInt());                tem.setC(scan.nextInt());                customer.add(tem);            }            Collections.sort(customer, new Comp().comparator);            System.out.println(customer);            int res = 0;            for (int i = 0; i < m; i++) {//用户批次                int loc = n;                if (desk.isEmpty()) {                    break;                }                for (int j = desk.size() - 1; j >= 0; j--) {                    int k = desk.get(j);                    int k1 = customer.get(i).num;                    if (desk.get(j) < customer.get(i).num) {                        break;                    } else {                        loc = j;                    }                }                if (loc != n) {                    res += customer.get(i).cost;//                  System.out.println(i+ "     " + customer.get(i).cost + "......" + loc);                    desk.remove(loc);                }            }            System.out.println(res);        }        scan.close();    }}class Group {    int num;    int cost;    public void setN(int n) {        this.num = n;    }    public void setC(int c) {        this.cost = c;    }    @Override    public String toString() {        return "num:" + num + " cost:" + cost;    }}class Comp {    Comparator<Group> comparator = new Comparator<Group>() {        public int compare(Group g1, Group g2) {            if (g1.cost < g2.cost) {                return 1;            } else if (g1.cost > g2.cost) {                return -1;            } else {                return 0;            }        }    };}

 

滴滴笔试题 就餐问题