[编程题]餐馆
- 热度指数：25420 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
某餐馆有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范围内。
输出描述:
输出一个整数,表示最大的总预计消费金额
示例1
输入
3 5 2 4 2 1 3 3 5 3 7 5 9 1 10
输出
20
java暴力破解
import java.util.*;
public class Main {
public static void main(String[] args) {
class Tmp{
int b;
int c;
}
Scanner sc = new Scanner(System.in);
long ans = 0;
int n = sc.nextInt();
int m = sc.nextInt();
// 桌子的最大容纳人数
int[] a = new int[n];
Tmp[] tmp = new Tmp[m];
for (int i = 0; i < m; i++) {
tmp[i] = new Tmp();
}
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
// 先用小桌子
Arrays.sort(a);
for (int i = 0; i < m; i++) {
tmp[i].b = sc.nextInt();
tmp[i].c = sc.nextInt();
}
// 把钱进行降序排序从而能取到最大值
Arrays.sort(tmp, new Comparator<Tmp>() {
@Override
public int compare(Tmp o1, Tmp o2) {
return o2.c - o1.c;
}
});
// 从坐的人最少的的开始找
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < tmp.length; j++) {
if(tmp[j].b <= a[i]){
ans += tmp[j].c;
tmp[j].b = Integer.MAX_VALUE;
tmp[j].c = 0;
break;
}
}
}
System.out.println(ans);
}
}
发表于 2023-03-03 19:08:03
回复(0)
用TreeMap保存桌子状态，客人消费从大到小排列。遍历客人时，比较map最大的键值和客人数，键值大就统计，然后更新map。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int m=sc.nextInt();
TreeMap<Integer,Integer> map=new TreeMap<>();
for(int i=0;i<n;i++){
int tmp=sc.nextInt();
map.put(tmp,map.getOrDefault(tmp,0)+1);
}
List<Node> node=new ArrayList<>();
for(int i=0,max=map.lastKey();i<m;i++){
int b=sc.nextInt();
int c=sc.nextInt();
if(b<=max){
node.add(new Node(b,c));
}
}
Collections.sort(node,new Comparator<Node>(){
@Override
public int compare(Node o1,Node o2){
return o2.getPrice()-o1.getPrice();
}
});
long sum=0l;
for(int i=0,j=0;i<n&&j<node.size();j++){
int num=node.get(j).getNumber();
int max=map.lastKey();
if(num<=max){
sum+=node.get(j).getPrice();
int key=map.ceilingKey(num);
int state=map.get(key);
if(state==1)
map.remove(key);
else
map.put(key,state-1);
i++;
}
}
System.out.println(sum);
}
sc.close();
}
}
class Node{
private int number;
private int price;
Node(int number,int price){
this.number=number;
this.price=price;
}
public int getNumber(){
return number;
}
public int getPrice(){
return price;
}
}
发表于 2021-03-18 14:05:57
回复(0)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main (String args[]) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int sum = 0;
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] desk = new int[n]; //桌子数组
for (int i = 0; i < n; i++) {
desk[i] = scanner.nextInt();
}
Arrays.sort(desk);
int[] renshu = new int[m]; // 客人的数量
int[] xiaofei = new int[m]; // 客人的消费金额
for (int i = 0; i < m; i++) {
int a = scanner.nextInt(); // 客人的数量
int b = scanner.nextInt(); // 客人的消费金额
renshu[i] = a;
xiaofei[i] = b;
}
//对客人的消费金额进行降序排序
for (int i = 0; i < xiaofei.length - 1; i++) {
for (int j = i; j < xiaofei.length; j++) {
if (xiaofei[i] < xiaofei[j]) {
int t = xiaofei[i];
int t1 = renshu[i];
renshu[i] = renshu[j];
renshu[j] = t1;
xiaofei[i] = xiaofei[j];
xiaofei[j] = t;
}
}
}
//对消费金额高的客户寻找合适的桌子
for (int i = 0; i < xiaofei.length; i++) {
for (int j = 0; j < desk.length; j++) {
if (desk[j] >= renshu[i]) {
sum += xiaofei[i];
desk[j] = 0;
renshu[i] = 0;
xiaofei[i] = 0;
break;
}
}
}
System.out.println(sum);
}
}
} 大佬们，哪里有问题呀 只能过40%
编辑于 2020-07-27 11:48:20
回复(0)
public class Main {
public static void main(String[] args) {
List<Integer> list=new ArrayList<>();
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int[] tab = new int[n];
int[][] cous = new int[m][2];
for (int i = 0; i < n; i++) {
tab[i] = scan.nextInt();
list.add(tab[i]);
}
Collections.sort(list);
Arrays.sort(tab);
int p=0;
for (int i = 0; i < m; i++) {
int x = scan.nextInt();
int y = scan.nextInt();
if (x<=tab[n-1]) {
cous[p][0]=x;
cous[p][1]=y;
p++;
}
}
Arrays.sort(cous, 0, p, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return b[1]-a[1];
}
});
long sum=0;
for (int i = 0; i < p; i++) {
int index=getTable(cous[i][0],list);
if (index!=-1) {
sum+=cous[i][1];
}
if (list.size()==0) {
break;
}
}
System.out.println(sum);
}
private static int getTable(int m, List<Integer> list) {
int l=0;
int r=list.size()-1;
if (list.get(r)<m) {
return -1;
}
int index=(l+r)/2;
while (l<=r) {
if (list.get(index)<m) {
l=index+1;
}
else {
r=index-1;
}
index=(l+r)/2;
}
if (list.get(index)<m&&index+1<list.size()) {
index++;
}
int ret = list.remove(index);
return ret;
}
}
public static void main(String[] args) {
List<Integer> list=new ArrayList<>();
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int[] tab = new int[n];
int[][] cous = new int[m][2];
for (int i = 0; i < n; i++) {
tab[i] = scan.nextInt();
list.add(tab[i]);
}
Collections.sort(list);
Arrays.sort(tab);
int p=0;
for (int i = 0; i < m; i++) {
int x = scan.nextInt();
int y = scan.nextInt();
if (x<=tab[n-1]) {
cous[p][0]=x;
cous[p][1]=y;
p++;
}
}
Arrays.sort(cous, 0, p, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return b[1]-a[1];
}
});
long sum=0;
for (int i = 0; i < p; i++) {
int index=getTable(cous[i][0],list);
if (index!=-1) {
sum+=cous[i][1];
}
if (list.size()==0) {
break;
}
}
System.out.println(sum);
}
private static int getTable(int m, List<Integer> list) {
int l=0;
int r=list.size()-1;
if (list.get(r)<m) {
return -1;
}
int index=(l+r)/2;
while (l<=r) {
if (list.get(index)<m) {
l=index+1;
}
else {
r=index-1;
}
index=(l+r)/2;
}
if (list.get(index)<m&&index+1<list.size()) {
index++;
}
int ret = list.remove(index);
return ret;
}
}
发表于 2018-09-30 13:53:14
回复(0)
贪心90%
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int []a = new int[n];
int [][] bc = new int[m][2];
for (int i = 0;i < n;i ++) {
a[i] = scanner.nextInt();
}
for (int i = 0;i < m;i ++) {
bc[i][0] = scanner.nextInt();
bc[i][1] = scanner.nextInt();
}
System.out.println(max(a, bc));
}
//贪心
public static long max(int []a, int [][] bc) {
Comparator comparator = new Comparator<int []>() {
@Override
public int compare(int[] o1, int[] o2) {
return o2[1] - o1[1];
}
};
Arrays.sort(bc, comparator);
// for (int i = 0;i < bc.length;i ++) {
// System.out.println(Arrays.toString(bc[i]));
// }
Arrays.sort(a);
// System.out.println(Arrays.toString(a));
int i = 0,j = 0;
long sum = 0;
int []used = new int[a.length];
//如果客人都坐好了，则结束循环
while (i < a.length && j < bc.length) {
if (a[i] >= bc[j][0] && used[i] == 0) {
sum += bc[j][1];
used[i] = 1;
j ++;
i = 0;
}else if (a[i] < bc[j][0] || used[i] != 0){
i ++;
}
//如果还没坐满，那么再次去匹配
if (i == a.length && !usedup(used)) {
i = 0;
j ++;
}
}
return sum;
}
public static boolean usedup(int []used) {
for (int i = 0;i < used.length;i ++) {
if (used[i] == 0) {
return false;
}
}
return true;
}
}
发表于 2018-05-27 22:36:53
回复(0)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner scan =new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
PriorityQueue<Integer> tableHeap = new PriorityQueue<>();
PriorityQueue<Guest> minHeap = new PriorityQueue<>();
MaxHeap<Guest> maxHeap = new MaxHeap<Guest>();
for(int i = 0;i<n;i++){
tableHeap.offer(scan.nextInt());
}
for(int i=0;i<m;i++){
minHeap.offer(new Guest(scan.nextInt(),scan.nextInt()));
}
long sum = 0l;
for(int i = 0;i<n;i++){
int tableCap = tableHeap.poll();
while(minHeap.peek()!=null&&minHeap.peek().num<=tableCap){
Guest guest = minHeap.poll();
guest.setComparable(guest.compFees);
maxHeap.offer(guest);
}
Guest guest = (Guest)maxHeap.poll();
if(guest==null){
continue;
}
sum+=guest.fees;
}
System.out.print(sum);
}
}
class MaxHeap<T extends Comparable> extends PriorityQueue{
MaxHeap (){
super(new Comparator<T>() {
@Override
public int compare(T o1, T o2) {
return -o1.compareTo(o2);
}
});
}
}
class Guest implements Comparable{
Comparable compNum = new CompNum();
Comparable compFees = new CompFees();
Comparable comparable =compNum;
int num;
int fees;
Guest(int num ,int fees){
this.num = num;
this.fees = fees;
}
public void setComparable(Comparable comparable) {
this.comparable = comparable;
}
@Override
public int compareTo(Object o) {
return comparable.compareTo(o);
}
class CompNum implements Comparable<Guest>{
@Override
public int compareTo(Guest o) {
return Guest.this.num-o.num;
}
}
class CompFees implements Comparable<Guest>{
@Override
public int compareTo(Guest o) {
return Guest.this.fees-o.fees;
}
}
}
桌子用最小堆维护，顾客一开始全放进另一个最小堆中，用人数num进行对比。每次从桌子的最小堆中拿出一个桌子记桌子容量tableCap，把存放顾客的最小堆中人数小于等于tableCap都加入顾客最大堆中，比较字段改成花费fees，加完后从最大堆弹出一个顾客，把它的花费加上。本质上是一个贪心算法。
编辑于 2018-04-21 16:19:38
回复(0)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
Table []table = new Table[n];
Customer [] customer = new Customer[m];
long sum = 0;
for(int i=0;i<n;i++){
int a = input.nextInt();
table[i] = new Table(a);
}
for(int i=0;i<m;i++){
int a = input.nextInt();
int b = input.nextInt();
customer[i] = new Customer(a,b);
}
Arrays.sort(table);
Arrays.sort(customer);
int count1 = 0;
for(int i=0;i<m;i++){
if(count1==n)break;
int l = 0;
int r = n-1;
while(l<=r){
int mid = l-(l-r)/2;
if(table[mid].num<customer[i].people)
l = mid+1;
else if(table[mid].num>customer[i].people)
r = mid-1;
else{
if(table[mid].flag==false){
sum+=customer[i].cost;
table[mid].flag = true;
count1++;
break;
}
else{
int temp = mid-1;
while(temp>=0&&table[temp].flag==true&&table[temp].num == table[mid].num)temp--;
if(temp>=0&&table[temp].flag==false&&table[temp].num == table[mid].num){
sum+=customer[i].cost;
table[temp].flag = true;
count1++;
break;
};
while(mid<=n-1&&table[mid].flag==true)mid++;
if(mid>n-1)break;
sum+=customer[i].cost;
table[mid].flag = true;
count1++;
break;
}
}
}
if(l>r){
while(l<=n-1&&table[l].flag==true)l++;
if(l<=n-1){
sum+=customer[i].cost;
table[l].flag = true;
count1++;
}
}
}
System.out.println(sum);
}
public static class Table implements Comparable<Object>{
int num;
boolean flag;
public Table(int num){
this.num = num;
flag = false;
}
@Override
public int compareTo(Object b) {
Table t = (Table)b;
if(this.num>t.num)
return 1;
else if(this.num<t.num)
return -1;
else
return 0;
}
}
public static class Customer implements Comparable<Object>{
int people;
int cost;
boolean flag;
public Customer(int people,int cost){
this.people = people;
this.cost = cost;
flag = false;
}
@Override
public int compareTo(Object o) {
Customer t = (Customer)o;
if(this.cost>t.cost)
return -1;
else if(this.cost==t.cost){
return this.people>t.people?1:-1;
}
else
return 1;
}
}
} 贪心思想，先对所有用餐人数进行一个排序，将消费最高的排最前，碰到消费相同的，按用餐人数升序排序；再对桌子进行一个排序，按最大容纳人数升序排序。依次对每批用餐人员处理：二分查找①先找到用餐人数跟桌子最大容纳人数相等的桌子，如果该桌子已经被使用，则找跟该桌子最大容纳人数相等的并且没有人坐的桌子，如果找到则坐下，标记桌子为已使用；如果发现跟该桌子最大容纳人数相等的桌子都已经被使用，则往容纳更多人数的桌子依次往上找，直到找到未使用的桌子坐下或没有桌子的时候停止；②如果mid没找到用餐人数跟桌子最大容纳人数相等的桌子，则l往容纳更多人数的桌子依次往上找，直到找到未使用的桌子坐下或没有桌子的时候停止；
当所有桌子已使用时可以提前停止。
发表于 2018-04-15 12:44:10
回复(0)
import java.util.*;
public class Main{
//插入到第一个容量大于等于target的地方,在处理连续相同值时取从最左边开始遍历，标准的对半搜索做不到的，（之前用Arrays.binarySearch怎么都不对，后来明白了）
public static int findTOInsert(int[] nums, int target){
int low = 0, hig = nums.length - 1,mid;
while(low <= hig){
mid = (low + hig) >>> 1;
if(nums[mid] >= target){
hig = mid - 1;
}else{
low = mid + 1;
}
}
return low;
}
public static long getMaxProfit(int []a,List<int[]> nums){
long sum = 0;
int left = a.length;
int k;
boolean[] status = new boolean[a.length];
for (int [] num : nums){
if (left == 0) break;
else {
k = findTOInsert(a,num[0]);
while (k < a.length && status[k]) k++;
if (k < a.length) {
status[k] = true;
left--;
sum += num[1];
}
}
}
return sum;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
List<int[]> nums = new ArrayList<>(m);
int b,c;
for (int i = 0; i < m; i++){
b = sc.nextInt();
c = sc.nextInt();
nums.add(new int[]{b,c});
}
Arrays.sort(a);
Collections.sort(nums,(int[] n1,int[] n2) -> n2[1] - n1[1]);
System.out.println(getMaxProfit(a,nums));
}
sc.close();
}
}
发表于 2018-02-02 19:24:50
回复(0)
public class Main{
//只通过40%，哪位大佬知道问题在哪吗？
public static void main(String[] args){
Scanner in= new Scanner(System.in);
while (in.hasNext()){
int n = in.nextInt();
int m = in.nextInt();
Vector<Integer> v = new Vector<Integer>();
for(int i=0; i<n; ++i){
int temp = in.nextInt();
v.add(temp);
}
Collections.sort(v);
int [][]customer = new int[m][2];
for(int i=0; i<m; ++i){
customer[i][0] = in.nextInt();
customer[i][1] = in.nextInt();
}
Arrays.sort(customer, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[1] > o2[1]) return -1;
else if (o1[1] == o2[1] && o1[0] > o2[0]) return -1;
return 0;
}
});
long count = 0;
//枚举，二分查找
for (int i=0; i<m; ++i){
int l = 0;
int r = v.size()-1;
if (v.size() == 0) break;
int temp = 0;
while (l<=r){
int mid = (r - l) /2 +l;
if(customer[i][0] <= (int)v.get(mid) ){
temp = customer[i][1];
v.remove(mid);
break;
}else{
l= mid +1;
}
}
count += temp;
}
System.out.println(count);
}
}
}
编辑于 2017-08-25 16:47:03
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int m = sc.nextInt();
int[] disk = new int[n]; //桌子数组
for (int i = 0; i < n; i ++) {
disk[i] = sc.nextInt();
}
Arrays.sort(disk); // 桌子容纳量从小到大排序
PriorityQueue<Customer> queue = new PriorityQueue<>(); // 将客人按消费额降序加入优先级队列
for (int i = 0; i < m; i ++) {
int b = sc.nextInt();
int c = sc.nextInt();
if(b <= disk[n - 1]) queue.add(new Customer(b, c)); // 如果人数小于桌子最大容纳量,加入队列
}
boolean[] visited = new boolean[n]; // 记录桌子是否被占用
long sum = 0; // 记录总盈利
int count = 0; // 记录已使用的桌子数
while ( ! queue.isEmpty()) {
Customer customer = queue.poll();
for (int i = 0; i < n; i ++) { // 为客人分配桌子
if(customer.peopleCount <= disk[i] && ! visited[i]) {
sum += customer.moneyCount;
visited[i] = true;
count ++;
break;
}
}
if(count == n) break;
}
System.out.println(sum);
}
}
static class Customer implements Comparable<Customer> {
private int peopleCount;
private int moneyCount;
public Customer(int peopleCount, int moneyCount) {
this.peopleCount = peopleCount;
this.moneyCount = moneyCount;
}
@Override
public int compareTo(Customer o) {
if(o.moneyCount > this.moneyCount) return 1;
else if(o.moneyCount < this.moneyCount) return - 1;
return 0;
}
}
}
编辑于 2017-02-10 12:14:05
回复(23)
问题信息
通过挑战的用户
查看代码-
2023-03-15 08:50:56
-
2022-11-07 12:02:05
-
2022-10-18 22:17:13
-
2022-10-15 17:55:35
-
2022-10-15 16:40:08
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
