免费网站下载大全,项目vi设计公司,推荐做网站的话术,wordpress主题授权加密1.火柴排队 思路
1.求最小值的时候#xff0c;可以直接按升序排序#xff0c;这样得到的值就是最小值 2.求最小交换次数的时候#xff0c;不能直接排序#xff0c;因为只能交换相邻的数#xff0c;只需要知道他们的相对大小#xff0c;所以可以先用离散化#xff0c;把…1.火柴排队 思路
1.求最小值的时候可以直接按升序排序这样得到的值就是最小值 2.求最小交换次数的时候不能直接排序因为只能交换相邻的数只需要知道他们的相对大小所以可以先用离散化把火柴高度映射成 1 到 n然后用一个中间数组 c让 b 数组按照 a 数组的顺序归并排序交换相邻两个元素最多只会使得逆序对数量减一
#includeiostream
#includealgorithm
using namespace std;
const int N 1e5 10, mod 99999997;
int a[N], b[N], c[N], d[N];
int n;// 离散化 a 和 b 数组
void init(int q[]){for(int i 1; i n; i) d[i] i;// d 数组根据 q 数组的大小关系排序sort(d 1, d n 1, [](int x, int y){return q[x] q[y];});for(int i 1; i n; i) q[d[i]] i;
}int merge_sort(int l, int r){if(l r) return 0;int mid (l r) / 2;int res (merge_sort(l, mid) merge_sort(mid 1, r)) % mod;int x 0, i l, j mid 1;while(i mid j r){if(b[i] b[j]) d[x] b[i];else{d[x] b[j];res (res mid - i 1) % mod;}}while(i mid) d[x] b[i];while(j r) d[x] b[j];for(int i l, j 0; j x; i, j) b[i] d[j];return res;
}int main(){scanf(%d, n);for(int i 1; i n; i) scanf(%d, a[i]);for(int i 1; i n; i) scanf(%d, b[i]);init(a), init(b);//for(int i 1; i n; i ) couta[i] ;//cout a endl;//for(int i 1; i n; i ) coutb[i] ;//cout b endl;// c 数组做为中间数组使得 a 数组是 有序的让 b 数组按照 a 数组的顺序进行归并排序for(int i 1; i n; i) c[a[i]] i;for(int i 1; i n; i) b[i] c[b[i]];//for(int i 1; i n; i ) coutb[i] ;//cout b endl;// 让 b 数组按照 a 数组的顺序进行归并排序int res merge_sort(1, n);printf(%d, res);return 0;
}2.归并排序 思路
模板题
#includeiostream
using namespace std;
const int N 1e5 10;
int a[N], b[N];
int n;void merge_sort(int l, int r){if(l r) return;int mid (l r) / 2;merge_sort(l, mid), merge_sort(mid 1, r);int x 0, i l, j mid 1;while(i mid j r){if(a[i] a[j]) b[x] a[i];else b[x] a[j];}while(i mid) b[x] a[i];while(j r) b[x] a[j];for(int i l, j 0; j x; i, j) a[i] b[j];
}int main(){scanf(%d, n);for(int i 0; i n; i) scanf(%d, a[i]);merge_sort(0, n - 1);for(int i 0; i n; i) printf(%d , a[i]);return 0;
}3.逆序对的数量 思路
模板题
#includeiostream
using namespace std;
const int N 1e5 10;
int a[N], b[N];
int n;
long long res;void merge_sort(int l, int r){if(l r) return;int mid (l r) / 2;merge_sort(l, mid), merge_sort(mid 1, r);int x 0, i l, j mid 1;while(i mid j r){if(a[i] a[j]) b[x] a[i];else{res 1ll * mid - i 1;b[x] a[j];}}while(i mid) b[x] a[i];while(j mid) b[x] a[j];for(int i l, j 0; j x; i, j) a[i] b[j];
}int main(){scanf(%d, n);for(int i 0; i n; i) scanf(%d, a[i]);merge_sort(0, n - 1);printf(%lld, res);return 0;
}4.小朋友排队 思路
k 队逆序对最少交换次数就是 k对于每个数k1 表示左边有多少个比它大的k2 表示右边有多少个比它小的所有数的 k1 和 k2 加起来 2 * k最小就是 2 * k也就是逆序对数量的两倍所以一共交换 1 2 3 … k1 k2那么不高兴程度之和就是每个位置的 (1 k1 k2) * (k1 k2) / 2 之和
#includeiostream
using namespace std;
const int N 1e5 10;
pairint, int a[N], b[N]; // 存储值和下标
long long sum[N];
int n;void merge_sort(int l, int r){if(l r) return;int mid (l r) / 2;merge_sort(l, mid), merge_sort(mid 1, r);int x 0, i l, j mid 1;while(i mid j r){// 加上后面比 a[i] 小的数if(a[i].first a[j].first){sum[a[i].second] j - mid - 1;b[x] a[i];}else{// 加上前面比 a[j] 大的数sum[a[j].second] mid - i 1;b[x] a[j];}}while(i mid){sum[a[i].second] j - mid - 1;b[x] a[i];}while(j r) b[x] a[j];for(int i l, j 0; j x; i, j) a[i] b[j];
}int main(){scanf(%d, n);int x;for(int i 0; i n; i){scanf(%d, x);a[i] make_pair(x, i);}merge_sort(0, n - 1);long long res 0;for(int i 0; i n; i) res (1 sum[i]) * sum[i] / 2;printf(%lld, res);return 0;
}5.超快速排序 思路
逆序对的数量模板题
#includeiostream
using namespace std;
const int N 5e5 10;
int a[N], b[N];
int n;
long long res;void merge_sort(int l, int r){if(l r) return;int mid (l r) / 2;merge_sort(l, mid), merge_sort(mid 1, r);int x 0, i l, j mid 1;while(i mid j r){if(a[i] a[j]) b[x] a[i];else{res 1ll * mid - i 1;b[x] a[j];}}while(i mid) b[x] a[i];while(j mid) b[x] a[j];for(int i l, j 0; j x; i, j) a[i] b[j];
}int main(){while(scanf(%d, n) n){for(int i 0; i n; i) scanf(%d, a[i]);merge_sort(0, n - 1);printf(%lld\n, res);res 0;}return 0;
}
