首页 > 代码库 > 滴滴笔试题 就餐问题
滴滴笔试题 就餐问题
题目:餐馆有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; } } };}
滴滴笔试题 就餐问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。