📄 maxguest.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>最大访客数</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 最大访客数</a></h1>
<h2>说明</h2>
现将举行一个餐会，让访客事先填写到达时间与离开时间，为了掌握座位的数目，必须先估计不同时间的最大访客数。<br>
<h2>解法</h2>
这个题目看似有些复杂，其实相当简单，单就计算访客数这个目的，同时考虑同一访客的来访时间与离开时间，反而会使程式变得复杂；只要将来访时间与离开时间分开处理就可以了，假设访客 i 的来访时间为x[i]，而离开时间为y[i]。<br>
<br>
在资料输入完毕之后，将x[i]与y[i]分别进行排序（由小到大），道理很简单，只要先计算某时之前总共来访了多少访客，然后再减去某时之前的离开访客，就可以轻易的解出这个问题。 <br>
<br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br>#define MAX 100 <br>#define SWAP(x,y) {int t; t = x; x = y; y = t;} <br><br>int partition(int[], int, int); <br>void quicksort(int[], int, int); // 快速排序法<br>int maxguest(int[], int[], int, int); <br><br>int main(void) { <br> int x[MAX] = {0}; <br> int y[MAX] = {0}; <br> int time = 0; <br> int count = 0; <br><br> printf("\n输入来访与离开125;时间(0~24)："); <br> printf("\n范例：10 15"); <br> printf("\n输入-1 -1结束"); <br> while(count < MAX) { <br> printf("\n>>"); <br> scanf("%d %d", &x[count], &y[count]); <br> if(x[count] < 0) <br> break; <br> count++; <br> } <br><br> if(count >= MAX) { <br> printf("\n超出最大访客数(%d)", MAX); <br> count--; <br> } <br><br> // 预先排序 <br> quicksort(x, 0, count); <br> quicksort(y, 0, count); <br><br> while(time < 25) { <br> printf("\n%d 时的最大访客数：%d", <br> time, maxguest(x, y, count, time)); <br> time++; <br> } <br><br> printf("\n"); <br><br> return 0; <br>} <br><br>int maxguest(int x[], int y[], int count, int time) { <br> int i, num = 0; <br><br> for(i = 0; i <= count; i++) { <br> if(time > x[i]) <br> num++; <br> if(time > y[i]) <br> num--; <br> } <br><br> return num; <br>} <br><br>int partition(int number[], int left, int right) { <br> int i, j, s; <br><br> s = number[right]; <br> i = left - 1; <br><br> for(j = left; j < right; j++) { <br> if(number[j] <= s) { <br> i++; <br> SWAP(number[i], number[j]); <br> } <br> } <br><br> SWAP(number[i+1], number[right]); <br> return i+1; <br>} <br><br>void quicksort(int number[], int left, int right) { <br> int q; <br><br> if(left < right) { <br> q = partition(number, left, right); <br> quicksort(number, left, q-1); <br> quicksort(number, q+1, right); <br> } <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>import java.io.*;<br>import java.util.*;<br><br>public class MaxVisit {<br> public static int maxGuest(int[] x, int[] y, int time) {<br> int num = 0; <br><br> for(int i = 0; i < x.length; i++) { <br> if(time > x[i]) <br> num++; <br> if(time > y[i]) <br> num--; <br> } <br><br> return num; <br> }<br> <br> public static void main(String[] args) throws IOException {<br> BufferedReader buf = new BufferedReader(<br> new InputStreamReader(System.in));<br> System.out.println("输入来访时间与离开时间(0~24)：");<br> System.out.println("范例：10 15"); <br> System.out.println("输入-1结束");<br> <br> java.util.ArrayList list = new ArrayList();<br> <br> while(true) { <br> System.out.print(">>"); <br> String input = buf.readLine();<br> <br> if(input.equals("-1")) <br> break; <br> <br> list.add(input);<br> }<br> <br> int[] x = new int[list.size()];<br> int[] y = new int[list.size()];<br> <br> for(int i = 0; i < x.length; i++) {<br> String input = (String) list.get(i);<br> String[] strs = input.split(" ");<br> <br> x[i] = Integer.parseInt(strs[0]);<br> y[i] = Integer.parseInt(strs[1]);<br> }<br> <br> Arrays.sort(x);<br> Arrays.sort(y);<br> <br> for(int time = 0; time < 25; time++) { <br> System.out.println(time + " 时的最大访客数：" <br> + MaxVisit.maxGuest(x, y, time)); <br> } <br> }<br>}</pre>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -