바 이 두 의 별 2015 첫 경기 (1) 1003 시퀀스 변환

시퀀스 변환 
 Accepts: 816
 
 Submissions: 3578
 Time Limit: 4000/2000 MS (Java/Others)
 
 Memory Limit: 32768/32768 K (Java/Others)
Problem Description
주어진 서열 A = {A1, A2,..., An} 은 서열 A 중의 일부 요 소 를 바 꾸 고 엄격 하고 단조 로 운 서열 B (엄격 하고 단조 로 운 정 의 는 bi < bi + 1, 1 ≤ i < N) 를 형성 하도록 요구 합 니 다.
우 리 는 서열 A 에서 서열 B 로 변환 하 는 대 가 를 cost (A, B) = max (| Ai − Bi |) (1 ≤ i ≤ N) 로 정의 합 니 다.
조건 을 만족 시 키 는 최소한 의 대 가 를 요구 하 다.
모든 원 소 는 변환 전후 에 정수 임 을 주의 하 세 요.
Input
제1 행위 테스트 의 그룹 수 T (1 ≤ T ≤ 10).
각 조: 첫 번 째 행위 서열 A 의 길이 N (1 ≤ N ≤ 105), 두 번 째 줄 은 N 개 수, A1, A2,..., An. 서열 A 중의 모든 요소 의 값 은 정수 이 며 106 을 초과 하지 않 습 니 다.
Output
모든 테스트 샘플 에 대해 두 줄 을 출력 합 니 다:
첫 번 째 줄 출력: "Case \ # i:".i. i 조 테스트 데 이 터 를 대표 합 니 다.
두 번 째 줄 에서 하나의 정 수 를 출력 하 는 것 은 조건 을 만족 시 키 는 최소 대 가 를 대표 한다.
Sample Input

2
2
1 10
3
2 5 4

Sample Output

Case #1:
0
Case #2:
1

문제 풀이 방향:
금 함유량 이 꽤 있 는 문제 다.
우선 등가, 문제 "조건 을 만족 시 키 는 최소 대가" (그 중 대 가 는 cost (A, B) = max (| Ai - Bi |) (1 < = i < = N) 는 등가 로 "주어진 배열 로 하 나 를 찾 을 수 있 습 니 다.Ai - i 의 최대 값 과 최소 값 을 찾 아 최소 값 이 최대 값 앞 에 나타 나 면 이 배열 의 최소 대 가 는 0 이 고, 최대 값 이 최소 값 앞 에 나타 나 면 (max - min) / 2 + (max - min)% 2 가 최소 대가 입 니 다. "
이런 사고방식 은 수학 귀납법 으로 증명 할 수 있다. 나 는 이런 사고방식 이 예 를 들 어 관찰 한 다음 에 부분적으로 귀납 한 다 는 것 을 알 수 있다.

#include 

int main()
{
    int T, N, i, j, k;
    scanf("%d", &T);
    for(i = 0; i < T; i++) {
        scanf("%d", &N);
        int cost, m, bestCost = 0;
        scanf("%d", &m);
        int min = m, max = m, minJ = 0, maxJ = 0;
        for(j = 1; j < N; j++) {
            scanf("%d", &m);
            m = m - j;
            if(m <= min) {min = m; minJ=j;}
            else if(m > max) {max = m; maxJ=j;}
        }
        if(maxJ < minJ) bestCost = max - min;
        printf("Case #%d:
", i+1);
        printf("%d
", bestCost / 2 + bestCost % 2);
    }
    return 0;
}