說明
現將舉行一個餐會，讓訪客事先填寫到達時間與離開時間，為了掌握座位的數目，必須先估計不同時間的最大訪客數。
解法
這個題目看似有些複雜，其實相當簡單，單就計算訪客數這個目的，同時考慮同一訪客的來訪時間與離開時間，反而會使程式變得複雜；只要將來訪時間與離開時間分開處理就可以了，假設訪客 i 的來訪時間為x[i]，而離開時間為y[i]。
在資料輸入完畢之後，將x[i]與y[i]分別進行排序（由小到大），道理很簡單，只要先計算某時之前總共來訪了多少訪客，然後再減去某時之前的離開訪客，就可以輕易的解出這個問題。
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
int partition(int[], int, int);
void quicksort(int[], int, int); // 快速排序法
int max(int[], int[], int, int);
int main(void) {
printf("\n輸入來訪與離開125;時間(0~24)：");
printf("\n範例：10 15");
printf("\n輸入-1 -1結束");
int x[MAX] = {0};
int y[MAX] = {0};
int count = 0;
while(count < MAX) {
printf("\n>>");
scanf("%d %d", &x[count], &y[count]);
if(x[count] < 0)
break;
count++;
}
if(count >= MAX) {
printf("\n超出最大訪客數(%d)", MAX);
count--;
}
// 預先排序
quicksort(x, 0, count);
quicksort(y, 0, count);
int time = 0;
while(time < 25) {
printf("\n%d 時的最大訪客數：%d", time, max(x, y, count, time));
time++;
}
printf("\n");
return 0;
}
int max(int x[], int y[], int count, int time) {
int num = 0;
int i;
for(i = 0; i <= count; i++) {
if(time > x[i])
num++;
if(time > y[i])
num--;
}
return num;
}
int partition(int number[], int left, int right) {
int s = number[right];
int i = left - 1;
int j;
for(j = left; j < right; j++) {
if(number[j] <= s) {
i++;
SWAP(number[i], number[j]);
}
}
SWAP(number[i+1], number[right]);
return i + 1;
}
void quicksort(int number[], int left, int right) {
if(left < right) {
int q = partition(number, left, right);
quicksort(number, left, q-1);
quicksort(number, q+1, right);
}
}
import java.io.*;
import java.util.*;
class Visitor {
final Integer startTime;
final Integer endTime;
Visitor(Integer startTime, Integer endTime) {
this.startTime = startTime;
this.endTime = endTime;
}
}
class Visitors {
private List<Integer> startTimes = new ArrayList<Integer>();
private List<Integer> endTimes = new ArrayList<Integer>();
Visitors(List<Visitor> visitors) {
for(Visitor v : visitors) {
startTimes.add(v.startTime);
endTimes.add(v.endTime);
}
Collections.sort(startTimes);
Collections.sort(endTimes);
}
int max(int time) {
int num = 0;
for(int i = 0; i < startTimes.size(); i++) {
if(time > startTimes.get(i))
num++;
if(time > endTimes.get(i))
num--;
}
return num;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
System.out.println("輸入來訪時間與離開時間(0~24)：");
System.out.println("範例：10 15");
System.out.println("輸入-1 -1結束");
List<Visitor> visitors = new ArrayList<Visitor>();
String input = null;
do {
System.out.print(">>");
input = buf.readLine();
String[] times = input.split(" ");
visitors.add(
new Visitor(new Integer(times[0]), new Integer(times[1])));
} while(!input.equals("-1 -1"));
Visitors vs = new Visitors(visitors);
for(int time = 0; time < 25; time++) {
System.out.printf("%d 時的最大訪客數：%d%n", time, vs.max(time));
}
}
}
def maxGuest(x, y, time):
num = 0
for i in range(len(x)):
if time > x[i]:
num += 1
if time > y[i]:
num -= 1
return num
print("輸入來訪時間與離開時間(0~24)：");
print("範例：10 15");
print("輸入-1結束");
list = []
while True:
xy =input(">>")
if xy == "-1":
break;
list.append(xy)
x = [0] * len(list)
y = [0] * len(list)
for i in range(len(x)):
xy = list[i].split(" ")
x[i] = int(xy[0])
y[i] = int(xy[1])
x.sort()
y.sort()
for time in range(25):
print(time, " 時的最大訪客數：", maxGuest(x, y, time))
case class Visitor(startTime: Int, endTime: Int)
class Visitors(visitors: List[Visitor]) {
private val startTimes = (for(v <- visitors) yield v.startTime).sort(_ < _)
private val endTimes = (for(v <- visitors) yield v.endTime).sort(_ < _)
def max(time: Int) = {
var num = 0
for(i <- 0 until startTimes.length) {
if(time > startTimes(i)) num += 1
if(time > endTimes(i)) num -= 1
}
num
}
}
println("輸入來訪時間與離開時間(0~24)：")
println("範例：10 15")
println("輸入-1 -1結束")
var visitors: List[Visitor] = Nil
var input = ""
do {
print(">>")
input = readLine()
val times = input.split(" ")
visitors = Visitor(times(0).toInt, times(1).toInt) :: visitors
} while(input != "-1 -1")
val vs = new Visitors(visitors)
for(time <- 0 to 24) {
printf("%d 時的最大訪客數：%d%n", time, vs.max(time));
}
# encoding: Big5
def maxGuest(x, y, time)
num = 0
x.length.times { |i|
if time > x[i]
num += 1
end
if time > y[i]
num -= 1
end
}
num
end
puts "輸入來訪時間與離開時間(0~24)："
puts "範例：10 15"
puts "輸入-1結束"
list = []
while true
print ">>"
xy = gets.chomp
if xy == "-1"
break
end
list << xy
end
x = Array.new(list.length, 0)
y = Array.new(list.length, 0)
x.length.times { |i|
xy = list[i].split(" ")
x[i] = xy[0].to_i
y[i] = xy[1].to_i
}
x.sort!
y.sort!
25.times { |time|
print time, " 時的最大訪客數：" , maxGuest(x, y, time), "\n"
}
|
|