#题解#洛谷 P4375 Out of Sorts G #离散化#

P4375 [USACO18OPEN] Out of Sorts G - 洛谷

分析

1. 注意到排序跟只跟数据的序相关，我们将原始数据离散化，并将数值更新为序

2. 不难注意到：每次moo只冒泡一次，对于每一个前缀子区间，会将较大的冒泡到末尾；由此不难想到：对于每个前缀子区间，要想让其内部有序，要冒泡的次数为区间内部大于末尾的数据的个数；那么最终moo次数就是max(1,每个前缀和冒泡次数)

3. 现在将目光放到冒泡两次：从左向右如同2；从右向左,会将每一个后缀子区间中最小的数放到正确的位置；综合两次冒泡：当数据的序大于输入顺序时，moo一次

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
struct data
{int val, num;//数值和输入顺序friend bool operator<(data x, data y){if (x.val == y.val)return x.num < y.num;return x.val < y.val;}
} a[N];
int n, ans = 1, cnt;
int vis[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++)cin >> a[i].val, a[i].num = i;sort(a + 1, a + 1 + n);for (int i = 1; i <= n; i++){if (i < a[i].num) cnt++;if (vis[i]) cnt--;vis[a[i].num] = 1;ans = max(ans, cnt);}cout << ans;return 0;
}