한 식당 에는 n 개의 책상 이 있 고 모든 책상 에는 하나의 매개 변수 a 가 수용 할 수 있 는 최대 인원 을 나타 내 며 m 의 손님 이 있 으 며 모든 손님 은 두 개의 매개 변수 가 있 으 며 b 는 인원 을 나타 내 고 c 는 예상 소비 금액 이다.
14172 단어 프로 그래 밍 문제
『 8195 』 짝 짓 기 가 허용 되 지 않 는 상황 에서 하나의 알고리즘 을 실현 하여 그 중의 일부 손님 을 선택 하여 총 예상 소비 금액 이 가장 많 습 니 다.
입력 설명:
* 8195 입력 은 m + 2 줄 을 포함 합 니 다.
첫째 줄 두 정수 n (1 < = n < = 50000), m (1 < = m < = 50000)
『 8195 』 두 번 째 행위 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.
코드 구현:
import java.util.Arrays;
import java.util.Scanner;
/**
* ：
* ， ，
**/
/**
*
*/
class Table implements Comparable {
//
public int number;
//
public boolean flag;
public Table(int number) {
this.number = number;
this.flag = false;
}
/**
* Table
* @param o
* @return
*/
@Override
public int compareTo(Object o) {
Table t = (Table) o;
if (this.number > t.number) {
return 1;
} else if (this.number == t.number) {
return 0;
} else {
return -1;
}
}
}
/**
*
*/
class Customer implements Comparable {
//
public int number;
//
public int spent;
//
public boolean flag;
public Customer() {}
public Customer(int number, int spent) {
this.number = number;
this.spent = spent;
flag = false;
}
/**
* ， ，
* @param o
* @return
*/
@Override
public int compareTo(Object o) {
Customer t = (Customer)o;
if (this.spent > t.spent) {
return -1;
} else if (this.spent < t.spent) {
return 1;
} else {
// return this.number>=t.number ? 1 : 0;
if (this.number > t.number) {
return 1;
} else if (this.number < t.number) {
return -1;
} else {
return 0;
}
}
}
}
public class RestaurantProblem {
public static void main(String[] args) {
// Scanner scanner = new Scanner(System.in);
// //
// int n = scanner.nextInt();
// //
// int m = scanner.nextInt();
// //
// Table[] tables = new Table[n];
// //
// Customer[] customers = new Customer[m];
//
// //
// for (int i = 0; i < n; i++) {
// tables[i] = new Table(scanner.nextInt());
// }
// //
// for (int i = 0; i < m; i++) {
// customers[i] = new Customer(scanner.nextInt(), scanner.nextInt());
// }
// scanner.close();
//
int n = 3;
//
int m = 5;
//
Table[] tables = new Table[n];
tables[0] = new Table(2);
tables[1] = new Table(4);
tables[2] = new Table(2);
//
Customer[] customers = new Customer[m];
customers[0] = new Customer(1, 3);
customers[1] = new Customer(3, 5);
customers[2] = new Customer(3, 7);
customers[3] = new Customer(5, 9);
customers[4] = new Customer(1, 10);
//
long sumSpent = 0;
// tables
Arrays.sort(tables);
// customers ， ，
Arrays.sort(customers);
//
int count = 0;
/**
* ( )
* 1. ，
* ， ， ，
* ， ，
* 2. mid ， l ，
* 。
*/
for (int i = 0; i < m; i++) {
//
if (count == n) {
break;
}
int l = 0;
int r = n-1;
while (l <= r) {
int mid = l+(r-l)/2;
// mid
if (tables[mid].number < customers[i].number) {
l = mid+1;
} else if (tables[mid].number > customers[i].number) {
// mid
r = mid-1;
} else {
//
if (!tables[mid].flag) {
sumSpent += customers[i].spent;
tables[mid].flag = true;
count++;
break;
} else{
//
int temp = mid-1;
//
while (temp>=0
&& tables[temp].flag==true
&& tables[temp].number==tables[mid].number) {
temp--;
}
// ，
if(temp>=0
&& tables[temp].flag==false
&& tables[temp].number == tables[mid].number){
sumSpent += customers[i].spent;
tables[temp].flag = true;
count++;
break;
}
// ， ，
while(mid<=n-1
&& tables[mid].flag==true) {
mid++;
}
// ，
if(mid > n-1) {
break;
}
//
sumSpent += customers[i].spent;
tables[mid].flag = true;
count++;
break;
}
}
}
// ， l
if(l>r){
//
while(l<=n-1
&& tables[l].flag==true) {
l++;
}
if(l<=n-1){
sumSpent += customers[i].spent;
tables[l].flag = true;
count++;
}
}
}
System.out.println(sumSpent);
}
}
좋은 웹페이지 즐겨찾기
