當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

【归并排序】休息（jzoj 3462）

發(fā)布時(shí)間：2023/12/3 编程问答 29 豆豆

生活随笔收集整理的這篇文章主要介紹了【归并排序】休息（jzoj 3462）小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

休息

jzoj 3462

題目大意

給你一個(gè)序列，你每一回合把它劃分成盡可能少的單調(diào)遞減的序列（第一次劃分到的序列長(zhǎng)度都是偶數(shù)），然后把每個(gè)序列翻轉(zhuǎn)，問你把它變成單調(diào)遞增的序列要翻轉(zhuǎn)多少次

輸入樣例

6 5 3 2 1 6 4

輸出樣例

樣例解釋

第一次劃分之后，翻轉(zhuǎn)(5,3,2,1)，（6,4）。之后，書的高度為1 2 3 5 4 6，然后便是翻轉(zhuǎn)（5,4）即可。

數(shù)據(jù)范圍

對(duì)于10%的數(shù)據(jù)： $n?50n\leqslant 50$
對(duì)于40%的數(shù)據(jù)： $n?3000n\leqslant 3000$
對(duì)于100%的數(shù)據(jù)： $1?n?100000,1?Hi?n1\leqslant n\leqslant 100000, 1\leqslant H_i\leqslant n$

解題思路

因?yàn)樗谝淮蝿澐值淖有蛄虚L(zhǎng)度都大于1所以，翻轉(zhuǎn)后只有序列之間的兩個(gè)數(shù)肯能會(huì)遞減，所以之后的翻轉(zhuǎn)次數(shù)就是它的逆序?qū)?#xff08;每個(gè)逆序?qū)Χ挤D(zhuǎn)一次，這個(gè)畫一下圖大概就可以理解了）

代碼

#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)//翻轉(zhuǎn) {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)//歸并排序求逆序?qū)?/span> {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);//最后一個(gè)序列不能忘s(1, n);printf("%lld", ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【归并排序】休息（jzoj 3462）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

JZOJ