逆序对排序;
字符串遍历;
pair
特点:
两个值,第一个是字符串,第二个是逆序对数。而且没有重复的字符串。
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=1e3+5;
#define x first
#define y secondpair<string,ll>a[N];ll count(string s)
{ll sum=0;for(ll i=0;i<s.size();i++){for(ll j=i+1;j<s.size();j++){if(s[j]<s[i])sum++;//对于一个字符串的比较,这个很重要}}return sum;
}
bool cmp(pair<string,ll>&a,pair<string,ll>&b)
{if(a.y!=b.y) return a.y<b.y;else if(a.x.size()!=b.x.size()) return a.x.size()<b.x.size();else return a.x<b.x;
}int main()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i].x;for(int i=1;i<=n;i++) a[i].y=count(a[i].x);sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++) cout<<a[i].x<<"\n";return 0;
}
重载运算符:
自定义的结构体的比较一般都搭配重载运算符(重载运算符不能运算自定义的)
重载运算符放在结构体内部定义,在sort排序时候会自动调用。
operate是一个重载关键字
第08课【 C++运算符重载】运算符重载,特殊重载,operator隐式转换,[]和()重载_哔哩哔哩_bilibili
//官方题解
#include<bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 1e3 + 10;int n;
struct Node
{string str;int k;bool operator< (const Node& p) const{if (k != p.k)return k < p.k;if (str.size() != p.str.size())return str.size() < p.str.size();return str < p.str;}
}q[N];
string tmp;
int res;void merge_sort(string &q, int l, int r)
{if (l >= r)return;int mid = l + r >> 1;merge_sort(q, l, mid), merge_sort(q, mid + 1, r);int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r)if (q[i] <= q[j])tmp[k ++ ] = q[i ++ ];elsetmp[k ++ ] = q[j ++ ], res += mid - i + 1;while (i <= mid)tmp[k ++ ] = q[i ++ ];while (j <= r)tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; j < k; ++ i, ++ j )q[i] = tmp[j];
}int main()
{tmp = string(N, ' ');cin >> n;for (int i = 0; i < n; ++ i ){string str;cin >> str;string s = str;res = 0;merge_sort(s, 0, s.size() - 1);q[i] = {str, res};}sort(q, q + n);for (int i = 0; i < n; ++ i )cout << q[i].str << endl;return 0;
}