Algorithm5 Advanced Sort
[TOC]
排序变种
- 结构体排序
- 结构体封装题目要求的实体
- 结构体封装大数的类，来进行运算
- 排序过程：计算交换次数
- 交换任意一对 => 一遍扫，模拟即可
- 仅可以交换相邻的 => 树状数组 // 归并排序
用优先队列实现的顶部最大 & 顶部最小
最大：priority_queue<int, vector<int>, greater<int>> pq;
最小：priority_queue<int> pq;
https://www.luogu.com.cn/problem/P3378
#include <iostream>
using namespace std;
#include <queue>
priority_queue<int, vector<int>, greater<int>> pq;
int m, op, t;
int main() {
scanf("%d", &m);
while (m--) {
scanf("%d", &op);
switch (op) {
case 1: scanf("%d", &t);pq.push(t);break;
case 2: printf("%d\n", pq.top());break;
case 3: pq.pop();break;
}
}
return 0;
}
结合结构体的排序 && 直接利用优先队列实现的排序
https://www.luogu.com.cn/problem/P1068
题目大意：按照成绩选人【多个】，但是每个人有编号和成绩两个属性是相互绑定的，所以用结构体储存很好。
考点：如果选人的个数是一个的话直接遍历==>区分下面的宇宙总统，宇宙总统就是选一个，但是比较的元素是大数，考点在大数；而这个题选人的个数是多个=>一边遍历就不合适了，直接排序即可。
而此题是
1、重载运算符，结合优先队列，直接根据成绩进行排名。 // 或者根据向量+sort排序，但是这样重载运算符的时候有区别。
2、**易错：重载的时候，成绩相同看看其他属性有没有要求。**=>如果成绩相同，编号小的靠前。
struct node {
int id, score;
node(int id, int score): id(id), score(score){}
bool operator < (const node n) const{
if (score == n.score)
return id > n.id;
return score < n.score;
}
};
题目链接：https://www.luogu.com.cn/problem/P1086
捡花生：数量最多：
题目大意：是给一个地图，地图上的某些点有一定数量的花生。给定一个步数范围拿到最多的花生。【纯数据结构可以解决，结构体+重载运算符+优先队列】
1、通过结构体储存地图上的点 2、按照每个点上的花生的个数来排序 3、从多到少遍历，并通过步数判断是否能采摘到下一个点
#include <iostream>
using namespace std;
int m, n, k, tem, sum = 0, ans = 0;
struct node {
int x, y, val;
node(int x, int y, int val): x(x), y(y), val(val){}
bool operator <(const node n) const{
return val < n.val;
}
};
#include <queue>
priority_queue<node> pq;
#include <cmath>
int main() {
scanf("%d%d%d", &m, &n, &k);
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
scanf("%d", &tem);
if (tem) pq.push(node(i, j, tem));
}
node ls = pq.top();
sum += (1+ls.x+1);
while (!pq.empty()){
node ls = pq.top();pq.pop();
if (sum + (ls.x+1) > k) break;
ans += ls.val;
node nt = pq.top();
if (sum + (abs(nt.x-ls.x) + abs(nt.y-ls.y) + nt.x+1) > k) break;
sum += (abs(nt.x-ls.x) + abs(nt.y-ls.y) + 1);
}
printf("%d\n", ans);
return 0;
}
大数比较 && 字符串比较
https://www.luogu.com.cn/problem/P1781
题目大意：选出一个数组中最大的数以及这个数的索引
1、比较大数=>先比较长度，长度想通了再逐位比较。
2、由于最新版C++支持将string转换为高精度浮点数比较，可以直接进行string的大小号比较。也就是直接将字符串in和字符串maxstr进行比较，来看是否要更新in > maxstr
int insize = in.size(), maxsize = maxstr.size();
if (insize > maxsize || (insize == maxsize && in > maxstr)) {
maxid = i+1;
maxstr = in;
}
大数乘除法 && 结构体排序
https://www.luogu.com.cn/problem/P1080
题目大意：若干个node，每个node都有左边和右边两个数。计算的数是排在每个node之前的所有node的左边的数相乘除以这个node的右边的数。=>要让这个最小，就需要进行结构体排序
1、结构体排序
bool operator < (const node n) const{
if (r == n.r) return l > n.l;
return r > n.r;
// 或者
// return l*r > n.l*n*r; // 可以根据数学推导推出
}
2、由于要把前面所有人的乘起来，位数爆炸。开long long也不够用。
因此要通过封装大数乘法来乘/除。
字符串拼接 & 字符串比较
https://www.luogu.com.cn/problem/P1012
题目大意：给出若干个字符串（长度不等长），要求拼接出一个字符串，这个字符串所代表的数最大。
1、单个字符串和单个字符串之间不好比较，转换成(单个字符串a+单个字符串b)与(单个字符串b+单个字符串a)的比较，这样就方便比较两个字符串拼接顺序，拼接无非就是先a后b或者先b后a，所以这样固定住了。
2、结合sort直接对string strs[maxn];进行排序即可。封装好bool cmp()函数。
#include <iostream>
using namespace std;
int n;
#define maxn 25
string strs[maxn];
#include <algorithm>
bool cmp(string a, string b){
return a+b > b+a;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) cin>>strs[i];
sort(strs, strs+n, cmp);
for (int i = 0; i < n; ++i) cout<<strs[i];
return 0;
}
排序求最少交换次数 - 任意一对
https://www.luogu.com.cn/problem/P1327
排序求最少交换次数 - 仅限相邻
题目类型：
- 【P1908】逆序的对数 =》 3 2 1的逆序的对数为32 31 21
- 【P1774】相邻两个交换，最后得到单调递增的序列的交换次数 =》3 2 1，首先213，把和3为逆序的都依次交换
https://www.luogu.com.cn/problem/P1908
https://www.luogu.com.cn/problem/P1774
归并排序解法
#include <iostream>
using namespace std;
const int maxn = 5e5+9;
typedef long long ll;
int n, a[maxn], t[maxn], tidx, lidx, ridx;
ll ans;
void mergesort(int l, int r){
if (r > l) {
int mid = (l+r)>>1;
mergesort(l, mid);
mergesort(mid+1, r);
tidx = lidx = l, ridx = mid+1;
while (lidx <= mid && ridx <= r) {
if (a[lidx] <= a[ridx]) t[tidx++] = a[lidx++];
else t[tidx++] = a[ridx++], ans += (mid-lidx+1);
}
while (lidx <= mid) t[tidx++] = a[lidx++];
while (ridx <= r) t[tidx++] = a[ridx++];
for (int i = l; i <= r; ++i) a[i] = t[i];
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a+i);
mergesort(1, n);
printf("%lld\n", ans);
return 0;
}
离散化+树状数组解法