ZOJ 1201

继续刷水题。看到这道题目有印象，想想，貌似当初算法是想出来了。就是自己想写个链表却有 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;
}