test.cpp

#include <iostream>
using namespace std;

void print_int_array(int a[], int length) { // helper function to print array
    for(int i = 0; i < length; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main() {
    // Part 1: Declare corresponding variables
    int seat_number_list[20] = {0};
    int seat_perference_list[20] = {0};
    int seat_number_to_index[21] = {0};
    bool seat_occupied_list[20] = {false};
    int n, index, occupied, k;
    bool found;

    // Part 2: Print number and perference of n seats

    //// Part 2.1: Receive n and check if n is in range
    cout << "Number of seats n in [5,20] = ? ";
    cin >> n;
    while(n < 5 || n > 20) { // if n out of range [5, 20]
        cout << "!!WRONG!! Please input an integer in [5,20] = ? "; // print error message
        cin >> n; // receive new n
    } // would loop until n is in range [5, 20]

    //// Part 2.2: Generate seat number and perference
    index = 0;
    int odd_max = (n % 2 == 0) ? n-1 : n; // largest odd number in the seats, which would be the number of first seat
    for(int odd_number = odd_max; odd_number > 0; odd_number -= 2) { // generate odd part
        seat_number_list[index] = odd_number;
        seat_number_to_index[odd_number] = index;
        seat_perference_list[index] = index + 1;
        index++;
    }
    for(int even_number = 2; even_number <= n; even_number += 2) { // generate even part
        seat_number_list[index] = even_number;
        seat_number_to_index[even_number] = index;
        seat_perference_list[index] = n - index;
        index++;
    }
    cout << "Seat number: ";
    print_int_array(seat_number_list, n);
    cout << "Seat preference: ";
    print_int_array(seat_perference_list, n);

    // Part 3: Print updated seat number and perference

    //// Part 3.1: Receive occupied seat no
    cout << "Occupied seat no.: ";
    do {
        cin >> occupied;
        if(occupied > 0 && occupied <= n){
            int occupied_index = seat_number_to_index[occupied];
            seat_occupied_list[occupied_index] = true;
        }
    } while(occupied != 0);

    //// Part 3.2: Print new seat number list
    cout << "Seat number: ";
    for(int i = 0; i < n; i++) {
        if(seat_occupied_list[i]){
            cout << "X";
        }
        else{
            cout << seat_number_list[i];
        }
        cout << " ";
    }
    cout << endl;

    //// Part 3.3: Print new seat perference list
    cout << "Seat perference: ";
    for(int i = 0; i < n; i++) {
        if(seat_occupied_list[i]){
            cout << "X";
        }
        else{
            cout << seat_perference_list[i];
        }
        cout << " ";
    }
    cout << endl;

    // Part 4: Search and print highest perference sum of k adjacent seats
    //// Part 4.1: Receive k
    cout << "How many adjacent seats to seek? ";
    cin >> k;

    ///// Part 4.2: Get highest perference sum
    int highest_perference = 0;
    int highest_perference_left_index = -1;
    for(int left_most_index = 0; left_most_index < n; left_most_index++) {
        int right_most_index = left_most_index + k - 1; // get index of right most chosen seat
        if(right_most_index >= n) { // if right_most_index is not smaller than n, then search is completed
            break;
        }
        bool skip = false;
        for(int i = left_most_index; i <= right_most_index; i++){ // scan through the chosen seats (from left_most to right_most)
            if(seat_occupied_list[i]){ // if any chosen seat is occupied
                skip = true; // skip flag
                break; // stop the scan, since we know the seats cannot be chosen
            }
        }
        if(skip) {
            continue;
        }
        int perference_sum = 0;
        for(int i = left_most_index; i <= right_most_index; i++){
            perference_sum += seat_perference_list[i];
        }
        if(perference_sum > highest_perference) {
            highest_perference = perference_sum;
            highest_perference_left_index = left_most_index;
        }
    }
    if(highest_perference > 0) {
        cout << "Best " << k << " adjacent " << ((k==1)?"seat":"seats") << ": no. ";
        int highest_perference_right_index = highest_perference_left_index + k - 1;
        for(int i = highest_perference_left_index; i <= highest_perference_right_index; i++){
            cout << seat_number_list[i] << ", ";
        }
        cout << "with total preference " << highest_perference << "." << endl;
    }
    else {
        // print sorry if not found
        cout << "Sorry! No " << k << " adjacent " << ((k==1)?"seat":"seats") << "!";
    }
    return 0;
}