休息

jzoj 3462

题目大意

给你一个序列，你每一回合把它划分成尽可能少的单调递减的序列（第一次划分到的序列长度都是偶数），然后把每个序列翻转，问你把它变成单调递增的序列要翻转多少次

输入样例

6 5 3 2 1 6 4

输出样例

3

样例解释

第一次划分之后，翻转(5,3,2,1)，（6,4）。之后，书的高度为1 2 3 5 4 6，然后便是翻转（5,4）即可。

数据范围

对于10%的数据：$n⩽50$
对于40%的数据：$n⩽3000$
对于100%的数据：$1⩽n⩽100000,1⩽H_i⩽n$

解题思路

因为它第一次划分的子序列长度都大于1所以，翻转后只有序列之间的两个数肯能会递减，所以之后的翻转次数就是它的逆序对（每个逆序对都翻转一次，这个画一下图大概就可以理解了）

代码

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll n, x, o, ans, a[100010], b[100010]; void fz(ll l, ll r)//翻转 {for (int i = 0; i < (r - l + 1)>>1; ++i)o = a[l + i], a[l + i] = a[r - i], a[r - i] = o; } void s(ll l, ll r)//归并排序求逆序对 {if (l >= r) return;ll mid = (l + r)>>1;s(l, mid);s(mid + 1, r);ll ls = l, rs = mid + 1, v = l;while(ls <= mid || rs <= r){if ((a[ls] < a[rs] || rs > r) && ls <= mid) b[v++] = a[ls++];else b[v++] = a[rs++], ans += mid - ls + 1;}for (int i = l; i <= r; ++i)a[i] = b[i]; } int main() {scanf("%lld", &n);x = 1;scanf("%lld", &a[1]);for (int i = 2; i <= n; ++i){scanf("%lld", &a[i]);if (a[i] > a[i - 1]) fz(x, i - 1), x = i, ans++;//划分子序列}ans++;fz(x, n);//最后一个序列不能忘s(1, n);printf("%lld", ans);return 0; }

总结

以上是生活随笔为你收集整理的【归并排序】休息（jzoj 3462）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。