目錄
前言
超快速排序
分析
代碼
小朋友排隊
分析
代碼
魚塘釣魚
分析
代碼
前言
本來計劃今天寫五道題的，結果計劃趕不上變化，誰能告訴我我的時間都去哪了。。。
今天給大家帶來三道題目，兩道逆序對問題，分別用歸并排序和樹狀數組求解，一道多路歸并。
超快速排序
分析
看完題目首先想到的是冒泡排序，但是顯然冒泡排序不屬于“超快速排序”。
但是既然題目的最終目的是排序，那就肯定離不開排序算法。
學過線性代數的同學都知道，有一個東西叫做逆序數，指的就是一組排列中逆序對的個數。
逆序對能不能和本題的“交換次數”聯系起來呢？主播很明確的告訴你們，最優的方案的交換次數就是逆序數。
如何證明呢？這個簡單。
我們知道，在一個排列中交換兩個相鄰的元素，造成的影響是逆序數加一或者減一。
而逆序數的含義可以視為，存在一種方案使得每次相鄰的兩個元素交換，都能使得逆序數減一。
接下來的問題就是證明這種方案存不存在，請觀察我下面的式子：
2， 3， 1
可以觀察到前兩個數字是已排序的，若要讓這個排列的逆序數歸零只需要交換3和1, 2和1，最終排列就變成了這樣
1, 2, 3
逆序數歸零了，并且我們每次交換操作造成的影響都是逆序數減一。
所以這種方案存在，具有充分性。
觀察原排列，可以發現原排列可以分為兩部分，即：2, 3 | 1，而每一部分內部都是排序過的。
觀察上方的排列，有沒有想起一個排序算法，沒錯，那么算法就是歸并排序。
我們都知道歸并排序是可以求逆序對數的，接下來主播就以自己的理解來解釋歸并排序為什么能夠求逆序對數。
首先，我們將一個排列的逆序對視為一個集合S
隨后，我們將排列分為兩個區間，對集合進行劃分，劃分為區間內的逆序對和區間間的逆序對。
至于為什么可以劃分很好證明，只需要證明三個子集沒有包含關系即可，通過反證法很好證明。
那么整體的逆序對數就等于區間內的逆序對數 + 區間間的逆序對數。（容斥原理）
而歸并排序就是利用這種思想，先消除區間內的逆序對，再消除區間間的逆序對，來達到計算逆序對數的效果。
而我們知道歸并排序處理的每個區間都是排序后的兩部分，所以根據上面的充分性，消除這樣的區間的逆序對數的交換次數就是逆序對數。
所以問題就轉化成了歸并排序求逆序對數。
代碼
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 500010;
int n;
int a[N],tmp[N];
LL merge_sort (int l,int r) {if (l == r) return 0;int mid = l + r >> 1;LL ans = merge_sort (l,mid) + merge_sort (mid + 1,r);int i = l,j = mid + 1,k = 0;while (i <= mid && j <= r) {if (a[i] <= a[j]) tmp[k++] = a[i++];else {tmp[k++] = a[j++];ans += mid - i + 1;}}while (i <= mid) tmp[k++] = a[i++];while (j <= r) tmp[k++] = a[j++];for (int i = l,j = 0;i <= r;i++,j++) a[i] = tmp[j];return ans;
}
int main () {while (cin >> n,n) {for (int i = 1;i <= n;i++) cin >> a[i];cout << merge_sort (1,n) << endl;}return 0;
}小朋友排隊
分析
前面我們證明了逆序對數就是至少交換次數，但是這道題有寫不一樣，我們需要統計交換雙方需要交換的次數那顯然就不只是逆序對數了。
主播剛開始以為答案就是逆序對數乘以二，可是后來發現這個想法是錯誤的，因為每個元素的逆序對數只能代表他“主動”與別人交換的次數，并不能代表這個元素交換的次數，觀察下方案例。
3， 2， 1
通過觀察可以發現要想排序可以發現1要交換兩次，3要交換兩次，2也需要交換兩次。
要講明白一個知識點，主播需要先引入一個概念：
順序對（主播自己起的名字，也不知道對不對），與逆序對相反，不過區別是順序對指的是在這個元素之后小于這個元素的個數。
反過來看，對于后面的元素來說，可以將順序對拆分成n部分，而其中的每一部分就是對于該元素的一個逆序對。
而后面的元素要想消除自己的逆序對就一定要與當前元素進行交換，我們將這種行為視為消除該元素的順序對。
這樣就同時統計了每個元素主動交換和被動交換的所有情況，因為最開始行為是區間劃分，所以也無需判重。
主播這次是用樹狀數組實現，樹狀數組的寫法很暴力，就是對每個數字統計在他前面且比他大的數字。
代碼
// 樹狀數組求逆序對和順序對
#include<iostream>
#include<cstring>
/*#define y second
#define x first*/
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 100010, P = 1000010;
int n;
int h[N];
int tree[P];
int st[N];
int lowbit(int x)
{return x & -x;
}void insert(int i, int x)
{if(i >= P) return;tree[i] += x;insert(i + lowbit(i), x);
}int find(int x)
{if(x == 0) return tree[0];return tree[x] + find(x - lowbit(x));
}int main()
{scanf("%d", &n);for(int i = 1; i <= n;h[i]++, i++) scanf("%d", h + i);for(int i = 1; i <= n; i++){st[i] += i - 1 - find(h[i]); //找大于當前數字的insert(h[i], 1);}memset(tree, 0, sizeof(tree));for(int i = n; i >= 1; i--){st[i] += find(h[i] - 1); // 小于當前數字的insert(h[i], 1);}LL l = 0;for(int i = 1; i <= n; i++)l += ((st[i] + 1) * (LL)st[i]) / 2;printf("%lld", l);return 0;
}魚塘釣魚
分析
首先想到可以搜索，但是數據量很大，而且狀態也不好表示，所以先排除搜索。
首先先觀察整體，可以發現每次換魚塘只會消耗時間而不會帶來重復收益，所以貪心思路是至多到達一次此魚塘，即：一條路走下去，不要反復橫跳。（這種找最優解的題一般是先分析整體看有沒有明顯重復的部分，隨后就可以根據這些重復的部分確定貪心思路）。
隨后發現了在哪個位置釣魚的收益與時間無關，只和次數有關，接下來我們來思考一下能否將交換位置的時間剝離出來。
顯然是可以的，隨后我們可以枚舉終點位置，即：每次只在1 ~ x的魚塘內釣魚。
接下來就變成了多個鏈表求最優和的問題。
可以發現每一個位置都是一個等差數列，并且考慮到有多個位置，每個位置地位相當，我們考慮使用多路歸并算法。
有的人可能沒有聽說過這個算法，但其實這個算法很簡單，合并兩個有序數組用的就是多路歸并算法。
隨后根據等差數列的性質，最大的數字一定會出現在最表層，所以我們用堆來查找出外層的最大值依次增加即可。
代碼
// 貪心 + 多路歸并，枚舉1 ~ n,每次多路歸并查找
// 時間復雜度: n * t * logN, 時間肯定夠。
#include<iostream>
#include<cstring>
#include<queue>
#define s second
#define f first
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, T, mx;
int a[N], b[N], t[N], st[N];
priority_queue<PII> pq;int main()
{scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", a + i);for(int i = 0; i < n; i++) scanf("%d", b + i);for(int i = 1; i < n; i++) scanf("%d", t + i);scanf("%d", &T);for(int i = 0; i < n; i++) //枚舉從0到i{int s = 0, l = 0;pq = priority_queue<PII>(); //重構。memset(st, 0, sizeof(st)); for(int j = 0; j <= i; j++){pq.push({a[j], j}); s += t[j]; //第一部分貪心的時間}while(s < T){PII x = pq.top(); pq.pop();l += max(0, x.f); st[x.s]++; pq.push({a[x.s] - st[x.s] * b[x.s], x.s});s++;}mx = max(mx, l);} printf("%d", mx);return 0;
}
