|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <stack> using namespace std; #define INFINITE 1000000005 long long swapt = 0; void merge(int* a,int start,int mid,int end){ long long swaptimes = 0; vector<int> larr,rarr; for (int i = start; i <= mid; i++) { larr.push_back(a[i]); } larr.push_back(INFINITE); for (int i = mid+1; i <= end; i++) { rarr.push_back(a[i]); } rarr.push_back(INFINITE); int lcur = 0,rcur = 0; for (int cur = start; cur <= end; cur++) { if (larr[lcur] < rarr[rcur]) { a[cur] = larr[lcur]; swaptimes += abs(lcur - cur + start); lcur++; continue; }else{ a[cur] = rarr[rcur]; swaptimes += abs(rcur + mid + 1 - cur); rcur++; continue; } } swapt += swaptimes/2; } void mergesrt(int* a,int start,int end){ int mid = (start+end)/2; if (start < end) { mergesrt(a, start, mid); mergesrt(a, mid+1, end); merge(a,start,mid,end); } } int main(){ int n = 0; int seq[500005]; while (cin >> n && n) { swapt = 0; for (int i = 0; i < n; i++) { scanf(" %d",&seq[i]); } mergesrt(seq, 0, n-1); cout << swapt << endl; } return 0; } |
SXBK,总的交换次数会爆掉int。。。我他妈wa了一天
改造归并排序，保存交换次数就可以了
