ZeroJudge A813: Viewing City

On a street in Kaohsiung City, many houses of varying heights are lined up neatly in a row.

For two houses, A and B, if the heights of all other houses between houses A and B do not exceed the heights of houses A and B, then a person standing on house A can see house B.

ZeroJudge A813 題目解說

As shown in the diagram, there are five houses from left to right, with heights of 5, 2, 3, 4, and 4, respectively. When standing on the rightmost house, since the height of this house is 4, and all the other houses between it and the leftmost house (with a height of 5) have heights (2, 3, 4) that do not exceed the height of the house you are on (4) and the leftmost house (5), you can see the leftmost house. Similarly, you can also see the second house from the right.

Given the heights of all the houses on the street from left to right, with N houses, calculate the total number of other houses that a person standing on the k-th house can see, denoted as Ck. You need to find the sum C1+C2+⋯+CN.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The test data input consists of only two lines.
The first line contains a positive integer N, indicating that there are N houses on the street.
The second line contains N positive integers (H1, H2, …, HN), representing the height of each house from left to right.		Output a single line containing one integer, which represents the total number of other houses that each house can see, i.e., the sum C1+C2+⋯+CN.
2
1 1		2
3
1 2 3		4
5
5 2 3 4 4		14
ZeroJudge A813 Sample Test Cases

Thought Process

This problem requires using long long int to store data.

Declare an array of pair, which will serve as a temporary storage area. The principle of viewing from left to right and right to left is the same. This temporary storage area will be referred to as "Box".

Each time you reach a building, check if there is data in the Box. If there is no data, push the current building's height into the Box. Since the array's data type is Pair, the first field stores the building height, and the second field stores how many consecutive buildings have this height. If there is already data in the Box, run a while loop. In each iteration of the loop, focus on the last piece of data in the Box, referred to as Last. If Last is greater than the current building height, it means you can no longer move forward, so increment ans++ and break the while loop. If Last is less than the current building height, add Last.second to ans, which represents the number of buildings with this height, and then pop the Box. If Last is equal to the current building height, first add Last.second to ans, then increment Last.second. Also, if there is other data in the Box, increment ans++. In the case of equality, you do not need to push the current building height into the Box; in all other cases, you should push it back.

Sample Code－ZeroJudge A813: Viewing City

#include <iostream>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    vector<long long int>building;
    vector<pair<long long int, long long int>>box;
    cin >> N;
    long long int ans = 0;
    for (int i = 0; i<N; i++) {
        int tmp;
        cin >> tmp;
        building.push_back(tmp);
        if (box.empty()) {
            box.push_back(make_pair(tmp, 1));
        }
        else {
            long long int count = 0;
            bool push = true;
            while (true) {
                const int last = box.size()-1;
                if (box.empty()) break;
                if (box[last].first > tmp) {
                    count++;
                    break;
                }
                if (box[last].first == tmp) {
                    count += min(1, int(box.size()-1));
                    count += box[last].second;
                    box[last].second++;
                    push = false;
                    break;
                }
                if (box[last].first < tmp) {
                    count += box[last].second;
                    box.pop_back();
                }
            }
            if (push) box.push_back(make_pair(tmp, 1));
            ans += count;
        }
    }
    box.clear();
    for (int i = N-1; i>=0; i--) {
        const int tmp = building[i];
        if (box.empty()) {
            box.push_back(make_pair(tmp, 1));
        }
        else {
            long long int count = 0;
            bool push = true;
            while (true) {
                const int last = box.size()-1;
                if (box.empty()) break;
                if (box[last].first > tmp) {
                    count++;
                    break;
                }
                if (box[last].first == tmp) {
                    count += box[last].second;
                    count += min(1, int(box.size()-1));
                    box[last].second++;
                    push = false;
                    break;
                }
                if (box[last].first < tmp) {
                    count += box[last].second;
                    box.pop_back();
                }
            }
            if (push) box.push_back(make_pair(tmp, 1));
            ans += count;
        }
    }
    cout << ans << "\n";
}

//ZeroJudge A813
//Dr. SeanXD
Tags

Related Posts

Comments