?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
107604752 |
Contestant: Invincible06 |
1490F - 13 | C++17 (GCC 7-32) | Time limit exceeded on test 12 | 2000 ms | 13084 KB | 2021-02-16 19:16:36 | 2021-02-17 08:50:57 |
// Problem: F. Equalize the Array // Contest: Codeforces - Codeforces Round #702 (Div. 3) // URL: https://codeforces.com/contest/1490/problem/F // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; #pragma GCC optimize("O2") #define M 1000000007 #define ll long long int #define pb push_back #define pf push_front #define all(x) x.begin(), x.end() #define pob pop_back #define pof pop_front #define debug1(x) cout<<#x<<" "<<x<<endl; #define debug2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl; #define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl; #define present(c,x) ((c).find(x) != (c).end()) #define null NULL #define mp make_pair #define sz(x) (ll)x.size() #define fi first #define se second #define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define inf 1e18 //#define endl '\n' //unsigned seed = std::chrono::system_clock::now().time_since_epoch().count(); //shuffle (foo.begin(), foo.end(), std::default_random_engine(seed)); #define ordered_set tree<ll, null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> typedef pair<int, int> pii; #define pi (3.14159265358979323846264338327950288) template<typename T> void printv(const T& t) { std::copy(t.cbegin(), t.cend(), std::ostream_iterator<typename T::value_type>(std::cout, ", ")); cout<<endl; } ll modpower(ll a,ll b,ll c) { ll res=1; while(b) { if(b&1LL) res=(res*a)%c; a=(a*a)%c; b>>=1; } return res; } //-------------------------------Template--Above----------------------------------------------- void solve(){ ll n;cin>>n; vector<ll>v(n); unordered_map<ll,ll>m1; //ll count=0; for(ll i=0;i<n;i++){ cin>>v[i]; m1[v[i]]++; } vector<ll>freq; if(m1[v[0]]==n){ cout<<0<<endl; return; } for(auto it:m1){ freq.pb(it.se); } ll ans=inf; ll m=freq.size(); sort(all(freq)); vector<ll>pre(m,0); pre[0]=freq[0]; for(ll i=1;i<m;i++) pre[i]=pre[i-1]+freq[i]; ans=pre[m-2]; for(ll i=m-2;i>0;i--){ ll diff=m-1-i; ll curr=pre[i-1]+(pre[m-1]-pre[i])-diff*freq[i]; ans=min(ans,curr); } ll curr=(pre[m-1]-freq[0])-(m-1)*freq[0]; ans=min(ans,curr); cout<<ans<<"\n"; return; } int main() { boost ll t; // t=1; cin>>t; while(t--){ solve(); } return 0; }
?
?
?
?