PTA A_1101 Quick Sort

798236606

题目链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805366343188480

解：
递推法

1. #include <stdio.h>
   
2. 
   
3. int nums[100010];
   
4. int l_max[100010];
   
5. int r_min[100010];
   
6. int candi[100010];
   
7. 
   
8. int main(void)
   
9. {
   
10.         int i, n, count = 0;
    
11.         
    
12.         scanf("%d", &n);
    
13.         for (i = 0; i < n; i++)
    
14.                 scanf("%d", nums + i);
    
15.                
    
16.         l_max[0] = nums[0];
    
17.         r_min[n - 1] = nums[n - 1];
    
18.         
    
19.         for (i = 1; i < n; i++)
    
20.                 l_max[i] = (nums[i] > l_max[i - 1]) ? nums[i] : l_max[i - 1];
    
21. 
    
22.         for (i = n - 2; i >= 0; i--)
    
23.                 r_min[i] = (nums[i] < r_min[i + 1]) ? nums[i] : r_min[i + 1];
    
24.                
    
25.         for (i = 0; i < n; i++)
    
26.                 if ((nums[i] == l_max[i]) && (nums[i] == r_min[i]))
    
27.                         candi[count++] = nums[i];
    
28.         
    
29.         printf("%d\n", count);               
    
30.         for (i = 0; i < count; i++)
    
31.         {
    
32.                 printf("%d", candi[i]);
    
33.                
    
34.                 if (i + 1 < count)
    
35.                         putchar(' ');
    
36.         }               
    
37.         putchar('\n');
    
38.                         
    
39.         return 0;
    
40. }

复制代码