[USACO 2018 Ope G]Out of Sorts

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

她到目前为止最喜欢的算法是“冒泡排序”。这是Bessie最初的对长度为N的数组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得到一个有趣的观察现象：大的元素很快就会被拉到数组末尾，然而小的元素需要很长时间“冒泡”到数组的开头（她怀疑这就是为什么这个算法得名的原因）。为了实验和缓解这一问题，Bessie试着修改了她的代码，使代码在每次循环中向前再向后各扫描一次，从而无论是大的元素还是小的元素在每一次循环中都有机会被拉较长的一段距离。她的代码现在是这样的：

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]    for i = N-2 downto 0:       if A[i+1] < A[i]:          swap A[i], A[i+1]    for i = 0 to N-2:       if A[i+1] < A[i]:          sorted = false

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

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; pair <int, int> a[N]; int b[N]; int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i].first; a[i].second = i; } sort(a + 1, a + 1 + n); int ans = 0, cnt = 0; for (int i = 1; i <= n; ++i) { if (i < a[i].second) ++cnt; if (b[i]) --cnt; b[a[i].second] = 1; ans = max(ans, cnt); } cout << max(1, ans); }

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; bool b[N]; pair<int,int>a[N]; int main() { int n; scanf("%d",&n); for( int i=1;i<=n;i++ ) { scanf("%d",&a[i].first); a[i].second=i; } sort(a+1,a+1+n); int ans=0,cnt=0; for( int i=1;i<=n;i++ ) { if( i<a[i].second ) cnt++; if( b[i] ) cnt--; b[a[i].second]=1; ans=max(ans,cnt); } printf("%d",max(1,ans)); }

详情