USACO2018 open Silver Problem 1

中文题面：

留意着农场之外的长期职业生涯的可能性，奶牛Bessie开始在不同的在线编程网站上学习算法。

她到目前为止最喜欢的算法是“冒泡排序”。这是Bessie的对长度为N N的数组A A进行排序的奶牛码实现。

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

显然，奶牛码中的“moo”指令的作用只是输出“moo”。奇怪的是，Bessie看上去执着于在她的代码中的不同位置使用这个语句。

给定一个输入数组，请预测Bessie的代码会输出多少次“moo”。

输入格式（文件名：sort.in）：

输入的第一行包含N N（1≤N≤100,000 1≤N≤100,000）。接下来N N行描述了A[0]…A[N−1] A[0]…A[N−1]，每个数都是一个范围为0…10 9 0…109的整数。输入数据不保证各不相同。

输出格式（文件名：sort.out）：

输出“moo”被输出的次数。

输入样例：
5
1
5
3
8
2

输出样例：
4

供题：Brian Dean

官方题解：

#include <cstdio>
#include <algorithm>
using namespace std;

struct Entry {
  int index;
  int value;
};

Entry entries[100000];

int main() {
  int n;
  scanf("%d", &n);

  for (int i = 0; i < n; i++) {
    entries[i].index = i;
    scanf("%d", &entries[i].value);
  }

  sort(entries, entries + n, [](Entry a, Entry b) {
    // Break ties by making the smaller element be whichever
    // element was first in the array originally.
    return a.value < b.value || (a.value == b.value && a.index < b.index);
  });

  int answer = 0;
  for (int j = 0; j < n; j++) {
    // In terms of the notation from the above analysis, we have,
    // entries[j].index = i
    // j = a_i
    answer = max(answer, entries[j].index - j);
  }

  printf("%d\n", answer + 1);
}