보위 안 (경 동 2017 필기시험 문제)

전쟁 게임 의 중요 한 부분 이 곧 다가 올 것 이다. 이번 결 과 는 왕국의 생사존망 을 결정 하고 B 군 은 수도의 방 위 를 책임 질 것 이다.수 도 는 사면 이 산 으로 둘러싸 인 분지 에 위치 해 있 으 며, 주변 에 있 는 n 개의 작은 산 이 하나의 고 리 를 이 루 고 있 으 며, 조기 경보 조치 로 작은 B 는 작은 산 마다 관찰 초 소 를 설치 해 밤낮으로 주변 에서 발생 하 는 상황 을 지 켜 볼 계획 이다.외지 침입 사건 이 발생 하면 산꼭대기 의 초 소 는 봉화 연 기 를 피 울 것 이다. 만약 두 초소 가 있 는 산봉우리 사이 에 더 높 은 산봉우리 가 가 려 지지 않 고 둘 사이 에 연결 통로 가 있다 면 초 소 는 다른 산봉우리 의 봉화 연기 가 점화 되 었 는 지 관찰 할 수 있다.작은 산 이 고리 위 에 있 기 때문에 임의의 두 작은 산 사이 에 두 개의 서로 다른 연결 통로 가 존재 한다.위 와 같은 가 려 지지 않 는 조건 에서 한 산봉우리 위의 초소 에 불 을 붙 인 봉 연 은 적어도 한 통 로 를 통 해 다른 한 끝 에서 관찰 할 수 있다.임의의 인접 초소 에 대해 서 는 한쪽 초소 에서 불 이 붙 은 봉 연 기 를 발견 할 수 있 을 것 이다.소 B 가 설계 한 이런 보위 방안 의 중요 한 특징 중 하 나 는 상대방 의 봉화 초소 의 수량 을 관측 할 수 있다 는 것 이다. 그녀 는 네가 그녀 를 도와 이 문 제 를 해결 할 수 있 기 를 바란다.
입력 설명:  입력 중 여러 조 의 테스트 데이터 가 있 습 니 다. 각 조 의 테스트 데이터 의 첫 번 째 행 위 는 하나의 정수 n (3 < = n < = 10 ^ 6) 이 고 수도 주변의 작은 산 수량 이 며, 두 번 째 행 위 는 n 개의 정수 이 며, 순서대로 작은 산 의 높이 h (1 < = h < = 10 ^ 9) 로 표 시 됩 니 다. 출력 설명:  각 조 의 테스트 데 이 터 를 단독 줄 에서 서로 관찰 할 수 있 는 초소 의 대 수 를 출력 합 니 다.  예시 1 입력
5  1 2 4 5 3 출력
7. 문제 풀이 방향:
이 조 수 를 하나의 고리 로 둘 러 두 점 (A, B) 이 통신 할 수 있 는 지 를 판단 하 는 방법 은 이 두 점 사이 의 점 이 모두 이 두 점 보다 작은 지 (A 보다 작고 B 보다 작은 지) 하 는 것 이다.다른 사람의 해법 을 보고 분석 해 보 세 요... 
나 는 다른 사람의 생각 을 보 았 는데, 이 문 제 는 좀 비슷 하 다. leetcode No84. Largest Rectangle in Histogram
우 리 는 단조 로 운 체감 스 택 으로 할 수 있다. 문제 중의 예 를 들 어 1, 2, 4, 5, 3.
먼저 연속 중복 요소 가 없 는 상황 을 고려 한 다음 에 중복 요소 가 있 는 상황 을 말한다.  먼저 자 리 를 옮 겨 최대 치 5 를 첫 번 째 요소 (why?) 로 합 니 다. 이 럴 때 배열 은 5, 3, 1, 2, 4 입 니 다.
결 과 를 res = 0 으로 설정 합 니 다.  스 택 이 단조 로 운 재 귀 스 택 이기 때문에 5, 3, 1 순서대로 스 택 에 들 어 갑 니 다.이때 창고 꼭대기 원 소 는 1 입 니 다.이제 입 점 할 것 은 2 입 니 다.2 창고 꼭대기 원소 1 보다 크 면 창고 꼭대기 원소 1 의 왼쪽 (3), 오른쪽 (2).그러면 1 은 3 과 2 를 볼 수 있 고 두 쌍 이 있 습 니 다.res=2
1. 스 택 에서 나 오 면 스 택 의 꼭대기 요 소 는 3, 2 가 3 보다 작 습 니 다.그래서 2. 창고 에 들 어 갑 니 다.이 때 창고 꼭대기 원 소 는 2 입 니 다.다음 4 는 창고 에 들 어가 야 하고 4 는 창고 꼭대기 원소 2 보다 크다.그러면 스 택 꼭대기 요소 2 는 왼쪽 (3) 오른쪽 (4) 을 볼 수 있 습 니 다.res=2+2=4。창고 에서 나오다
같은 이치 로 3 은 창고 에서 나 오고 4 는 창고 에 들어간다.res=4+2=6。  이때 창고 안의 원 소 는 4 와 5 밖 에 없다.한 쌍 으로res=6+1=7。
중복 요소 가 있 는 경우 3, 1 (연속 n 개 1), 4 를 가정 합 니 다.이 n 개 1 은 모두 3 과 4 를 볼 수 있 고 2 * n 개가 있 으 며 이 n 개 1 은 서로 볼 수 있 기 때문에 Cn2 개가 있다.그래서 대 수 는 n * 2 + n * (n - 1) / 2 입 니 다.두 가지 요소 의 경우 1 (t1 개 1), 2 (t2 개 2), 대 수 는 t1 * t2 + t1 * (t1 - 1) / 2 + t2 * (t2 - 1) / 2 이다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define N 10006
using namespace std;


int main() {
	int n, maxVal = -5;
	stack > s; 
	long long res = 0;
	scanf("%d", &n);
	vector v(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		maxVal = max(maxVal, v[i]);
	}
	
	vector::iterator it = v.begin();
	while (*it != maxVal) {
		int temp = *it;
		it = v.erase(it);
		v.push_back(temp);
	}

	s.push(pair(v[0], 1));
	for (int i = 1; i < n; i++) {
		if (v[i] == s.top().first) {
			s.top().second++;
		} else if (v[i] < s.top().first) {
			s.push(pair(v[i], 1));
		} else {
			while (v[i] > s.top().first) {
				long long t = s.top().second;
				res += t * (t - 1) / 2 + 2 * t;
				s.pop();
			}
			if (v[i] == s.top().first) { 			//       ，     
				s.top().second++; 
			} else {
				s.push(pair(v[i], 1));
			}
		}
	}
	if (s.size() > 2) {
		while (s.size() > 1) {
			long long t = s.top().second;
			res += t * (t - 1) / 2 + 2 * t;
			s.pop();
		}
		long long t = s.top().second;
            res += t * (t - 1) / 2;
            s.pop();
	} else if (s.size() == 2){
            long long a = s.top().second;
            s.pop();
            long long b = s.top().second;
            s.pop();
            res += b * (b-1) / 2 + a * (a-1) / 2 + a * b;
        } else {
            long long t = s.top().second;
            res += t * (t - 1) / 2;   
            s.pop(); 
        }
        cout << res << endl;
	return 0;
}