关于一个摆动数列的问题

暮色沧绯

Problem Description已知递推数列：

                               
登录/注册后可看大图

试求该数列的第n项，并统计出前n项哪些项最大，最大值是多少？       
Input本题有多组测试数据，第一行是测试数据组数T，下面T行的每一行有一个整数n，表示所求的项。1<=n<=50000。       
Output输出共有T行，依次对应输入行。每行第一个数是第n项值，第2个数是前n项的最大值，紧接是数m，表示取最大值的项数，随后是m项的下标. 整数两两之间应有一个空格。       
Sample Input1500
Sample Output11 55 2 341 427 注意，本题有时间限制，Time Limit : 3000/1000ms   Memory Limit : 65535/32768K ，求最大值和个数合并成一个循环操作或者把求前n个的最大数放到循环外比较方便。拜托各位了！顺便，最好只用数组函数循环做，后面的还没学到……

仰望天上的光

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAX_NUM 50000
   
5. 
   
6. int* init();
   
7. void deal_all( int* pData );
   
8. void deal_one_time( int* pData, int n );
   
9. void destroy( int* pData );
   
10. 
    
11. int main( void ) {
    
12.         int* pData;
    
13.         pData = init();
    
14.         deal_all( pData );
    
15.         destroy( pData );
    
16. }
    
17. 
    
18. int* init() {
    
19.         //数组下标0不用
    
20.         int* result = (int*)malloc( (MAX_NUM+1) * sizeof(int) );
    
21.         return result;
    
22. }
    
23. 
    
24. void destroy( int* pData ) {
    
25.         free( pData );
    
26. }
    
27. 
    
28. void deal_all( int* pData ) {
    
29.         int times, i;
    
30.         scanf("%d",&times);
    
31.         for(i=0; i<times; ++i) {
    
32.                 int n;
    
33.                 scanf("%d", &n);
    
34.                 deal_one_time( pData, n );
    
35.         }
    
36. }
    
37. 
    
38. void deal_one_time( int* pData, int n ) {
    
39.         int max_vec[200]={1};//最大值下标数组
    
40.         int count=1;//最大值个数
    
41.         int pre_max = 1;//初始的最大值
    
42.         int i = 2;
    
43. 
    
44.         for( pData[1]=1; i <= n; ++i ) {
    
45.                 //求pData[i]
    
46.                 if( i%2==0 ) pData[i] = pData[i/2];
    
47.                 else pData[i] = pData[i/2] + pData[i/2+1];
    
48.                 //处理最大值
    
49.                 if( pData[i]>pre_max ) {
    
50.                         pre_max = pData[i];
    
51.                         count = 0;
    
52.                         max_vec[count++] = i;
    
53.                 }else if( pData[i] == pre_max ) {
    
54.                         max_vec[count++] = i;
    
55.                 }
    
56.         }
    
57. 
    
58.         //打印结果
    
59.         printf("%d %d %d ", pData[n], pre_max, count);
    
60.         for( i=0; i< count; ++i ) printf("%d ", max_vec[i]);
    
61.         printf("\n");
    
62. }

复制代码

仰望天上的光

如果可以使用结构体的话，程序结构可以清晰很多。

暮色沧绯

仰望天上的光 发表于 2012-11-20 15:13

                               
登录/注册后可看大图

如果可以使用结构体的话，程序结构可以清晰很多。

木有学……