最大访客数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#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 maxguest(int[], int[], int, int); 

int main(void) { 
    int x[MAX] = {0}; 
    int y[MAX] = {0}; 
    int time = 0; 
    int count = 0; 

    printf("\n输入来访与离开125;时间(0~24)："); 
    printf("\n范例：10 15"); 
    printf("\n输入-1 -1结束"); 
    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); 

    while(time < 25) { 
        printf("\n%d 时的最大访客数：%d", 
                   time, maxguest(x, y, count, time)); 
        time++; 
    } 

    printf("\n"); 

    return 0; 
} 

int maxguest(int x[], int y[], int count, int time) { 
    int i, num = 0; 

    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 i, j, s; 

    s = number[right]; 
    i = left - 1; 

    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) { 
    int q; 

    if(left < right) { 
        q = partition(number, left, right); 
        quicksort(number, left, q-1); 
        quicksort(number, q+1, right); 
    } 
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

import java.io.*;
import java.util.*;

public class MaxVisit {
    public static int maxGuest(int[] x, int[] y, int time) {
        int num = 0; 

        for(int i = 0; i < x.length; i++) { 
            if(time > x[i]) 
                num++; 
            if(time > y[i]) 
                num--; 
        } 

        return num; 
    }
    
    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结束");
        
        java.util.ArrayList list = new ArrayList();
        
        while(true) { 
            System.out.print(">>"); 
            String input = buf.readLine();
            
            if(input.equals("-1")) 
                break; 
            
            list.add(input);
        }
        
        int[] x = new int[list.size()];
        int[] y = new int[list.size()];
        
        for(int i = 0; i < x.length; i++) {
            String input = (String) list.get(i);
            String[] strs = input.split(" ");
            
            x[i] = Integer.parseInt(strs[0]);
            y[i] = Integer.parseInt(strs[1]);
        }
        
        Arrays.sort(x);
        Arrays.sort(y);
        
        for(int time = 0; time < 25; time++) { 
            System.out.println(time + " 时的最大访客数：" 
                    + MaxVisit.maxGuest(x, y, time)); 
        } 
    }
}