Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$
Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự bất kỳ sao cho số lượng cặp $a_i<a_i+1$ lớn nhất có thể
Lời giải: Đây là bài sử dụng map đặc trưng, từ đó ta thu được mảng cần tìm
Source:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- vector<ll> v;
- map<ll,ll> mt;
- int main(){
- ll n;
- cin>>n;
- ll i;
- for(i=0;i<n;i++){
- ll x;
- cin>>x;
- mt[x]++;
- }
- ll res=0;
- for(auto p: mt){
- res=max(res,p.second);
- }
- for(ll z=0;z<res;z++){
- for(auto p: mt){
- if(p.second!=0) {v.push_back(p.first); mt[p.first]--;}
- else continue;
- }
- }
- ll ans=0;
- for(i=1;i<v.size();i++)
- if(v[i]>v[i-1]) ans++;
- cout<<ans;
- return 0;
- }