1321.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1321 on 2005-03-23 at 23:14:11 */ 
#include <stdio.h>

int main()
{
    int pare[40], t, n, left[20], right[20], temp[20], total;
    int i, j, k, l, m, step;
    
    scanf("%d", &t);
    for(i = 0; i < t; i++){
        scanf("%d", &n);
        total = 2 * n;
        for(j = 0; j < n; j++){
            scanf("%d", &right[j]);
            if(j == 0){
                for(k = 0; k < right[0]; k++){
                    pare[k] = 0;
                }
                pare[k++] = 1;
            }else{
                m = right[j] - right[j-1];
                for(l = 0; l < m; l++, k++){
                    pare[k] = 0;
                }
                pare[k++] = 1;
            }
        }
        for(j = 0, k = 0, l = 0; j < total; j++){
            if(pare[j] == 0){
                temp[k++] = j;
            }else{
                right[l++] = j;
            }
        }
        for(j = 0; j < n; j++){
            for(k = n-1; k >= 0; k--){
                if((temp[k] < right[j]) && (temp[k] != -1)){
                    left[j] = temp[k];
                    temp[k] = -1;
                    break;
                }
            } 
        }
        for(j = 0; j < n; j++){
            if(j == 0){
                printf("1");
            }else{
                step = 0;
                for(k = 0; k <= j; k++){
                    if((left[k] >= left[j]) && (right[k] <= right[j])){
                        step++;
                    }
                }
                printf(" %d", step);
            }
        }
        printf("\n");
    }
    
    return 0;
}