연호 구간 수-블 루 브리지 컵

나의 새 블 로그 방문 을 환영 합 니 다.
주소
제목:연호 구간 수-블 루 브리지 컵
내용:2013 년 제4 회 블 루 브리지 컵 전국 소프트웨어 대회 예선,10 번.
저자:http://www.milkcu.com/blog/
제목 설명
제목:연호 구간 수 샤 오 밍 은 요 며칠 동안 이런 이상 하고 재 미 있 는 문 제 를 생각 하고 있다.1~N 의 한 전체 배열 에 몇 개의 연호 구간 이 있 을 까?여기 서 말 하 는 연결 구간 의 정 의 는 구간[L,R]에 있 는 모든 요소(즉,이 배열 의 L 번 째 부터 R 번 째 요소)가 정렬 을 늘 린 후에 R-L+1 길이 의'연속'수열 을 얻 을 수 있다 면 이 구간 의 연결 구간 이 라 고 한다.N 이 아주 어 렸 을 때 샤 오 밍 은 빠르게 답 을 계산 할 수 있 었 지만 N 이 커 졌 을 때 문 제 는 그리 간단 하지 않 았 다.지금 샤 오 밍 은 너의 도움 이 필요 하 다.입력 형식:첫 번 째 줄 은 정수 N(1<=N<=50000)으로 전체 배열 의 규 모 를 표시 합 니 다.두 번 째 줄 은 N 개의 서로 다른 숫자 Pi(1<Pi>=N)로 이 N 개의 숫자의 특정한 전체 배열 을 나타 낸다.출력 형식:하나의 정 수 를 출력 하여 서로 다른 연결 구간 의 수 를 표시 합 니 다.예시:사용자 입력:4,3,4 1 프로그램 은 출력 해 야 한다.7 사용자 입력:5,3,2,5 프로그램 은 출력 해 야 한다.9 설명:첫 번 째 사례 에서 7 개의 연결 구간 은[1,1],[1,2],[1,3],[3,3],[4,4]두 번 째 사례 에서 9 개의 연결 구역 간 이 각각[1,1],[1,2],[1,3],2,[3],[4,4],[5,5]이다.5]자원 약정:피크 메모리 소모<64M CPU 소모<5000 ms 요구 에 따라 출력 하 십시오."입력 하 십시오..."와 같은 불필요 한 내용 을 사족 으로 인쇄 하지 마 십시오.모든 코드 를 같은 원본 파일 에 넣 고 디 버 깅 을 통과 한 후 복사 하여 원본 코드 를 제출 합 니 다.메모:main 함 수 는 0 주 의 를 되 돌려 야 합 니 다.ANSI C/ANSI C++표준 만 사용 하고 컴 파일 환경 이나 운영 체제 에 의존 하 는 특수 함 수 를 호출 하지 마 십시오.메모:모든 의존 함 수 는 원본 파일 에 명확 하 게 있어 야 합 니 다.\#include는 프로젝트 설정 을 통 해 상용 헤더 파일 을 생략 할 수 없습니다.제출 할 때 원 하 는 컴 파일 러 형식 을 선택 하 십시오.
분석 하 다.
비록 이것 이 마지막 문제 이지 만 생각 이 정확 하 다 면 매우 간단 하 다.시험 을 볼 때 가장 어 리 석 은 방법 으로 요 소 를 꺼 내 고 정렬 하 며 판단 했다.
사실 이 문 제 는 아래 의 사상 으로 실현 할 수 있다.max-min=j-i.
코드 구현

# include <stdio.h>
int main(void)
{
	int n;
	int count = 0;
	scanf("%d", &n);
	int a[n];
	for(int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}

	for(int i = 0; i < n; i++) {
		int min = n;
		int max = 1;
		for(int j = i; j < n; j++) {
			if(min > a[j]) {
				min = a[j];
			}
			if(max < a[j]) {
				max = a[j];
			}
			if(max - min == j - i) {
				count++;
			}
		}
	}
	printf("%d
", count);
}

최종 답안
만나다
(전문 완료)