继续刷水题。看到这道题目有印象，想想，ms当初算法是想出来了。就是自己想写个链表却有bug，结果一直拖着没有解决。好歹前几天又研究了下STL，这下派上用场了。不过代码写的很乱，感觉不够优美，不beautiful。最后的输入输出有些小问题，导致第一次提交是Presentation Error。后来仔细看了看搞定。算了，先糊弄着看吧。15道了。还有285道。一道一道的啃。

具体解题思路就不写了。大概如下，如果是P，就进行双层循环，然后搞一个数组的索引（不知道该怎么说哎……）；如果是I，建立一个链表，从Inversion[]的最后一个元素开始循环，然后分别处理每个元素。根据Inversion[i]的数值遍历链表并插入合适的元素。最后的输入输出有问题。仔细看一下就行了。

#include <iostream>
#include <list>
using namespace std;

const int max_size = 50;

int main(int argc, char *argv[])
{
    int cases;
    char method;

    while (1)
    {
        cin >> cases;

        if (cases == 0)
        {
            break;
        }

        cin >> method;
        if (method == 'P')
        {
            int P[max_size], I[max_size];

            for (int i = 0; i < cases; ++i)
            {
                cin >> P[i];
                I[i] = 0;
            }
            for (int i = 0; i < cases; ++i)
            {
                for (int j = i + 1; j < cases; ++j)
                {
                    if (P[i] > P[j])
                    {
                        I[P[j]-1]++;
                    }
                }
            }
            for (int i = 0; i < cases - 1; ++i)
            {
                cout << I[i] << " ";
            }
            cout << I[cases - 1] << endl;
        }
        else if (method == 'I')
        {
            list<int> P;
            int I[max_size];

            for (int i = 0; i < cases; ++i)
            {
                cin >> I[i];
            }

            P.push_back(cases);
                        
            for (int i = cases - 2; i >= 0; --i)
            {
                list<int>::iterator it = P.begin();
                for (int j = 0; j < I[i]; j++)
                {
                    it++;
                }
                P.insert(it, i+1);
            }

            list<int>::iterator it;
            int i;
            
            for (i = 0, it = P.begin(); i < P.size() - 1; ++it, ++i)
            {
                cout << *it << " ";
            }
            
            cout << *it << endl;
        }
        else
        {
            break;
        }
    }
    
    return 0;
}

• Relative Posts