ACM 111 - History Grading

#include <stdio.h>

int main()
{
    int n, i, j;
    scanf("%d", &n);
    int grade[n], answer[n], r[n], b[n];
    for (i = 0; i < n; i ++)
        scanf("%d", &r[i]);
    for (i = 0; i < n; i ++)
         b[r[i] - 1] = i + 1;
    for (i = 0; i < n; i ++)
         answer[b[i]] = i;     
    while (1)
    {  
        if (scanf("%d", &r[0]) < 1) break;
        int max = 0, nowMax = 0;  
        for (i = 1; i < n; i ++)
            scanf("%d", &r[i]);
        for (i = 0; i < n; i ++)
            grade[r[i] - 1] = i + 1;  
        for (i = 0;i < n; i++)
            r[i] = answer[grade[i]];
        int best[n];
        int length = 1;
        best[0] = r[0];

        for (i = 1;i < n; i ++){
            for (j = 0;j < length;j ++){
                if (r[i] < best[j]){
                    best[j] = r[i];
                    break;
                }
            }
            if (r[i] > best[length - 1]){
                best[length++] = r[i];
            }
        }
        printf("%d\n",length);
    }
    return 0;
}

回目錄
回首頁