說明
現將舉行一個餐會,讓訪客事先填寫到達時間與離開時間,為了掌握座位的數目,必須先估計不同時間的最大訪客數。
解法
這個題目看似有些複雜,其實相當簡單,單就計算訪客數這個目的,同時考慮同一訪客的來訪時間與離開時間,反而會使程式變得複雜;只要將來訪時間與離開時間分開處理就可以了,假設訪客 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" }
|
|