レストラン問題
タイトルの説明
あるレストランにはnつのテーブルがあり、各テーブルにはパラメータがあります.aが収容できる最大人数です.mロットのお客様がいて、各ロットのお客様には2つのパラメータがあります:b人数、c予想消費金額.相席が許可されていない場合は、アルゴリズムを実装して一部のお客様を選択し、総予想消費金額が最大になるようにしてください.
説明を入力:
入力にはm+2行が含まれます.1行目の2つの整数n(1<=n<=50000)、m(1<=m<=50000)の2番目の動作n個のパラメータa、すなわち、各テーブルに収容可能な最大人数は、スペースで区切られ、範囲は32ビットintの範囲内である.次にm行、各行に2つのパラメータb,cを示す.第iロットのお客様の人数と予想消費金額をそれぞれ表し、スペースで区切られ、範囲は32ビットintの範囲内である.
問題解決のポイント:
本題は貪欲なアルゴリズムに似ていて、肝心な問題はどのように迅速に適切なテーブルを現在の波の客にマッチングするかで、テーブルを小さいから大きい順に並べて、それから遍歴する方法で適切なテーブルを探すことができますが、この方法はプログラムの時間の複雑さを大幅に増加させます.より速い方法は、このようなプログラムを二分法で検索する時間の複雑さが小さいことです.
あるレストランにはnつのテーブルがあり、各テーブルにはパラメータがあります.aが収容できる最大人数です.mロットのお客様がいて、各ロットのお客様には2つのパラメータがあります:b人数、c予想消費金額.相席が許可されていない場合は、アルゴリズムを実装して一部のお客様を選択し、総予想消費金額が最大になるようにしてください.
説明を入力:
入力にはm+2行が含まれます.1行目の2つの整数n(1<=n<=50000)、m(1<=m<=50000)の2番目の動作n個のパラメータa、すなわち、各テーブルに収容可能な最大人数は、スペースで区切られ、範囲は32ビットintの範囲内である.次にm行、各行に2つのパラメータb,cを示す.第iロットのお客様の人数と予想消費金額をそれぞれ表し、スペースで区切られ、範囲は32ビットintの範囲内である.
問題解決のポイント:
本題は貪欲なアルゴリズムに似ていて、肝心な問題はどのように迅速に適切なテーブルを現在の波の客にマッチングするかで、テーブルを小さいから大きい順に並べて、それから遍歴する方法で適切なテーブルを探すことができますが、この方法はプログラムの時間の複雑さを大幅に増加させます.より速い方法は、このようなプログラムを二分法で検索する時間の複雑さが小さいことです.
import java.util.*;
/**
*
*/
public class Main {
public static void main(String[] args) {
Scanner input =new Scanner(System.in);
// n , m
int n = input.nextInt();
int m = input.nextInt();
// n
long[] desks = new long[n];
for(int i = 0; i// m
Customer[] customers = new Customer[m];
for(int i = 0; inew Customer(input.nextLong(),input.nextLong());
}
//
Arrays.sort(customers,new Comparator(){
@Override
public int compare(Object o1, Object o2) {
if(((Customer) o1).getMonetary()>((Customer) o2).getMonetary()) {
return -1;
} else if(((Customer) o1).getMonetary()return 1;
}else {
return 0;
}
}
});
boolean[] desks_use = new boolean[n];
long sum = 0;
// ,
for(int i=0;iint index = bs(desks,customers[i].getTotle());
while (index < n && desks_use[index] ==true ){
index ++;
}
if(indextrue;
}
}
System.out.println(sum);
}
//
static int bs(long[] desks, Long tar){
int low=0;
int high=desks.length-1;
int mid;
while(low <= high){
mid=(high+low)>>1;
if(desks[mid]>=tar)
high=mid-1;
else
low=mid+1;
}
return low;
}
}
/**
*
*/
class Customer{
private Long totle;
private Long monetary;
public Customer(Long totle, Long monetary) {
this.totle = totle;
this.monetary = monetary;
}
public Long getTotle() {
return totle;
}
public Long getMonetary() {
return monetary;
}
public void setTotle(Long totle) {
this.totle = totle;
}
public void setMonetary(Long monetary) {
this.monetary = monetary;
}
}