hdoj 2404 Permutation Recovery【水水】

叁歲伎倆 2022-08-05 08:58 138阅读 0赞

# Permutation Recovery #

**Time Limit: 10000/4000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 445    Accepted Submission(s): 307**

题目大意：输入整数n，表示接下来要输入n个数（n为0时结束），输入n个数（这n个数为1-n），比如n8; a1=5, a2=0, a3=1, a4=2, a5=1, a6=2, a7=0, a8=0，其中，a1=5表示在数字以前面有5个数比他大，a2=0，表示2前面有零个数比他大，a3=1表示3前面有1个数比他大....以此类推，求出符合此规律的数列；

Sample Input

8	10
    5	9
    0	8
    1	7
    2	6
    1	5
    2	4
    0	3
    0	2
      
       
      
       
        
       	1
    	0
      
       
      
       
        
       	0

Sample Output

2,7,3,5,4,1,8,6
    10,9,8,7,6,5,4,3,2,1

思路：遍历数列a，开个数组k用来储存新数列，初始化为0，先从a1开始，比如说上面n=8的那个例子，a1= 5，；又因为1最小所以1前面有5个数，故从k\[1\]开始，数到第6个0，这个位子就填1，a2=0，所以k\[1\]=2；a3=1，所以从k\[1\]开始数，数到第a3+1个0,该位置就是填3...以此类推

已Accept代码【c++提交】

#include <iostream>
    #include <cstring>
    using namespace std;
    int m[504];
    int n, k, s;
    int main() {
        while(cin >> n, n) {
            memset(m, 0, sizeof(m));
            for(int i = 1; i <= n; i++) {	//输入一个，判断一个，这样可以少开一个数组，节约空间 
                cin >> k;
                int ok = 0;
                for(int j = 1; j <= n; j++) {
                    if(k == 0){					//输入的数为0时，从k[1]开始查找，找到第一个为零的，把i值赋给他； 
                        for(s = 1; m[s] != 0; s++);
                        m[s] = i;
                        break;
                    }
                    else{						//若不为零，则从k[1]开始数，数到第k+1个零是把值赋给他 
                        if(m[j] == 0)
                            ok++;
                        if(ok == k + 1) {
                            m[j] = i;
                            break;
                        }
                    }
                }
            }
            cout << m[1];
            for(int i = 2; i <= n; i++)
                cout << "," << m[i];
            cout << endl;
        }
        return 0;
    }