題目

傳送門 to usOJ

題目描述
下面是一段實現冒泡排序算法的 $\text{C++}$ 代碼：

for(int i=1; i<n; i++)for(int j=1; j<=n-i; j++)if(a[j] > a[j+1])swap(a[j],a[j+1]);

其中待排序的 $a$ 數組是一個 $1,2,3,\dots ,n$ 的排列，$\mathtt{s}\mathtt{w}\mathtt{a}\mathtt{p}$ 函數將交換數組中對應位置的值。

對于給定的數組 $a$ 以及給定的非負整數 $k$ ，使用這段代碼執行了正好 $k$ 次 $\mathtt{s}\mathtt{w}\mathtt{a}\mathtt{p}$ 操作之后數組 $a$ 中元素的值會是什么樣的呢？

輸入格式
輸入文件共 $2$ 行。第 $1$ 行包含空格隔開的一個正整數 $n$ 和一個非負整數 $k$ ；第$2$行包含 $n$ 個空格隔開的互不相同的正整數，表示初始時 $a$ 數組中的排列。

輸出格式
輸出文件共 $1$ 行。若在執行完整個代碼之后執行 $\mathtt{s}\mathtt{w}\mathtt{a}\mathtt{p}$ 的次數仍不夠 ，那么輸出一個字符串 $“\mathtt{I}\mathtt{m}\mathtt{p}\mathtt{o}\mathtt{s}\mathtt{s}\mathtt{i}\mathtt{b}\mathtt{l}\mathtt{e}!”$（不含引號），否則按順序輸出執行 $\mathtt{s}\mathtt{w}\mathtt{a}\mathtt{p}$ 操作 $k$ 次之后數組 $a$ 的每一個元素，用空格隔開。

數據范圍與約定

對于$100\%$的數據，$n\le 10^6,k\le 10^{12}$ 。

思路

給大家看一個 手畫的、丑的不堪入目的 冒泡排序過程圖——

旁邊的紅色標記是指針的意思（也就是所謂的$j$）。

你看，我們“冒泡”的過程，更像踢足球的過程。一開始球在 $3$ 手里，然后就被 $6$ 搶斷了；$6$ 一路過人，過掉了比自己弱的 $2,1,5,4$ ，然后又被 $7$ 搶斷了；$7$ 射門了！結果發現是自家的門。

球回到第一個人手里，再來一次。比如圖中的情況，$3$ 跑到了 $5$ 前面，$5$ 傳給了 $6$ ，$6$ 肝不動 $7$ ……

所以，明確這一點：“運球的球員”只會越來越大。

誰會過掉你呢？是比你大的人。而且在你前面。所以我們往逆序對這方面思考。

結論：將 $j$ 的循環（內層循環）跑一次叫做“一輪”，每一輪中，如果 $x$ 的左邊有比自己大的數字，那個比自己大的數字就會越過 $x$ ，其余數字的相對位置不變；否則 $x$ 就會向右移動。

首先，如果 $x$ 被越過了，每一輪最多只有一個數字會越過 $x$ 。因為只有一個數字在“運球”。

如果 $x$ 左邊有比它大的數字，球要么去了它手上，要么是一個比它還強的球員正在運球。無論怎樣，由于運球的球員越來越大，最終這個人一定會過掉 $x$ 。

反之，如果左邊沒有比 $x$ 強的球員，$x$ 一定會把球斷下來。

斷言：每一輪最多只有一個數字越過 $x$ ，其充要條件是 $x$ 左邊有比它大的數字；其余數字與 $x$ 的相對位置不變。

假設跑了 $\omega$ 輪，每一個數字會被多少個數字跨過？設 $b_x={\sum }_{i=1}^{x?1}[a_i>a_x]$ ，顯然有兩個限制條件：

• 答案不超過 $b_x$ 。因為左邊只有 $b_x$ 個數字可以越過它。
• 答案不超過 $\omega$ 。因為每一輪只有一個數字可以越過它。

所以答案就是 $\min (b_x,\omega )$ 。而 $\mathtt{s}\mathtt{w}\mathtt{a}\mathtt{p}$ 的本質就是一次跨越，我們將其記錄在被跨過的點身上，不難發現，跨越和 $\mathtt{s}\mathtt{w}\mathtt{a}\mathtt{p}$ 一一對應。于是總 $\mathtt{s}\mathtt{w}\mathtt{a}\mathtt{p}$ 次數就是 ${\sum }_{i=1}^n\min (b_i,\omega )$ 。

所以我們可以二分 $\omega$ 然后判斷，是否交換了至少 $k$ 次。于是我們就求出了跑了多少輪。

求出多少輪之后，我們只需要知道 $a$ 是什么樣子即可——最后一輪可以暴力模擬。

怎么求 $a$ 數組長什么樣子呢？

對于 $b_x\ge \omega$ 的 $x$ ，因為它左邊有 $\omega$ 個數字跨過了它，于是它就移步到了原位置向左移動 $\omega$ 步的地方。

把這些 $x$ 填好之后，就留下了一些坑，我們用剩下的數字來填。

剩下的數字是 $b_x<\omega$ 的 $x$ ，于是一定存在某個時刻，$x$ 的左邊已經沒有比它小的數了。逆序對是不增的，所以直到最后，$x$ 的左邊也沒有比它小的數。既然如此，剩下的數字中最小的一個，就會是最左邊的一個坑（否則更左邊的坑中就有了比它大的數字）；第二小，就是左數第二個坑；其余同理。

于是我們把剩下的數字存儲下來，排序，然后依次塞到坑里去。

時間復雜度：計算 $b$ 時可以使用樹狀數組，$\mathcal{O}(n\log n)$ ；二分與判斷，一共 $\mathcal{O}(n\log n)$ ；排序與填空，一共 $\mathcal{O}(n\log n)$ 。

代碼

#include <cstdio> #include <iostream> #include <vector> #include <algorithm> using namespace std; inline int readint(){int a = 0; char c = getchar(), f = 1;for(; c<'0' or c>'9'; c=getchar())if(c == '-') f = -f;for(; '0'<=c and c<='9'; c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f; } inline void writeint(long long x){if(x < 0) putchar('-'), x = -x;if(x > 9) writeint(x/10);putchar(x%10+'0'); }const int MaxN = 1000005; int a[MaxN], n; long long k;void input(){n = readint(); scanf("%lld",&k);for(int i=1; i<=n; ++i)a[i] = readint(); }int b[MaxN]; /* a[i]前面有多少個比a[i]小的數字 */ int BIT[MaxN]; /* 樹狀數組 */ void getB(){for(int i=1; i<=n; ++i){/* 經典問題：樹狀數組求逆序對 */b[i] = 0;for(int j=n+1-a[i]; j; j-=(j&-j))b[i] += BIT[j];for(int j=n+1-a[i]; j<=n; j+=(j&-j))++ BIT[j];} } long long check(int x){long long res = 0;for(int i=1; i<=n; ++i)res += min(x,b[i]);return res; } /* 多年準備一場空，不開 long long 見祖宗 */ int tmp[MaxN], bucket[MaxN]; void solve(){getB();int L = 0, R = n, mid;if(check(n) < k){ /* 即使跑n輪都搞不定k */puts("Impossible!");return;}while(L != R){ /* 二分唄，還能是啥 */mid = (L+R+1)>>1;if(check(mid) <= k)L = mid;else R = mid-1;}k -= check(L); /* 把前面那幾輪的swap次數減掉 */int jb = 0; /* 剩下的是嘉(jia)賓(bin) */for(int i=1; i<=n; ++i) /* 直接定位 or 收集 */if(b[i] >= L) tmp[i-L] = a[i];else bucket[++ jb] = a[i];sort(bucket+1,bucket+jb+1); /* 排序 */for(int i=1,ppl=1; i<=n; ++i) /* 填坑 */if(not tmp[i]) tmp[i] = bucket[ppl ++];swap(tmp,a); /* 將tmp拷貝給a，據說C++11就是O(1) */for(int i=1; i<n and k; ++i)if(a[i] > a[i+1]) /* 暴力模擬 */swap(a[i],a[i+1]), -- k;for(int i=1; i<=n; ++i)writeint(a[i]), putchar(' '); }int main(){freopen("sort.in","r",stdin);freopen("sort.out","w",stdout);input(), solve();return 0; }

總結

以上是生活随笔為你收集整理的[usOJ6310]冒泡排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。