~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
typedef pair<int,int> pi;↵
vector<int>arr;↵
bool pos(ll s,ll ride){↵
if(s<arr.back()) return 0;↵
ll r = 0;↵
multiset<int>st(arr.begin(),arr.end());↵
while(st.size()){↵
r++;↵
int cur = *st.begin();↵
if(cur>s) return 0;↵
st.erase(st.begin());↵
if(st.size()==0) break;↵
auto it = st.upper_bound(s-cur);↵
if(it==st.begin()) continue;↵
st.erase(prev(it));↵
}↵
return r<=ride;↵
}↵
ll f(ll ride){↵
ll l = 0;↵
ll r = INT32_MAX;↵
while(l<=r){↵
ll mid = (l+r)>>1;↵
if(!pos(mid,ride)) l = mid+1;↵
else r = mid-1;↵
}↵
return ride*l;↵
}↵
int main(){↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
int n; cin>>n;↵
map<int,int>m;↵
for(int i=1; i<=n; i++){↵
int a; cin>>a;↵
m[a]++;↵
}↵
for(auto p : m) arr.push_back(p.second);↵
sort(arr.begin(),arr.end());↵
if(arr.size()==1){↵
cout<<arr.back();↵
return 0;↵
}↵
ll ans = INT64_MAX;↵
for(int i=(arr.size()/2+arr.size()%2); i<=arr.size(); i++){↵
ans = min(ans,f(i));↵
}↵
cout<<ans;↵
}↵
~~~~~↵
↵
https://mirror.codeforces.com/problemset/problem/1250/B↵
↵
this problem has no editorial.↵
i just iterated all possible r and calculate minimum s with binary search↵
↵
doing binary search, i greedily tried to take two teams at one ride if it's possible.↵
if s is fixed and current team has c member, i checked whether there's a team with maximum number of members d <= (s-c) ↵
if there's such team, two team can ride together, otherwise just take one time at this ride. ↵
↵
is it logically wrong? or implementation is wrong? need help!↵
(also i wanna know if there's a solution with complexity k^2 or faster , since my code is too slow ) ↵
↵
↵
↵
↵
↵
UDP: another version that doesn't use binary search and multiset yet produces same Wrong Answer.↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
typedef pair<int,int> pi;↵
vector<int>arr;↵
int pointer;↵
↵
bool pos(ll s,ll ride){↵
if(s<arr.back()) return 0;↵
deque<int>deq(arr.begin(),arr.end());↵
ll ret = 0;↵
while(deq.size()){↵
ret++;↵
int sz = deq.back();↵
deq.pop_back();↵
if(deq.size() && deq.front()+sz<=s){↵
deq.pop_front();↵
}↵
}↵
return ret<=ride;↵
}↵
ll f(ll ride){↵
while(pos(pointer,ride)) pointer--;↵
pointer++;↵
return ride*pointer;↵
}↵
int main(){↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
int n; cin>>n;↵
map<int,int>m;↵
for(int i=1; i<=n; i++){↵
int a; cin>>a;↵
m[a]++;↵
}↵
for(auto p : m) arr.push_back(p.second);↵
sort(arr.begin(),arr.end());↵
if(arr.size()==1){↵
cout<<arr.back();↵
return 0;↵
}↵
↵
pointer = n;↵
ll ans = INT64_MAX;↵
for(int i=(arr.size()/2+arr.size()%2); i<=arr.size(); i++){↵
ans = min(ans,f(i));↵
}↵
cout<<ans;↵
}↵
~~~~~↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
typedef pair<int,int> pi;↵
vector<int>arr;↵
bool pos(ll s,ll ride){↵
if(s<arr.back()) return 0;↵
ll r = 0;↵
multiset<int>st(arr.begin(),arr.end());↵
while(st.size()){↵
r++;↵
int cur = *st.begin();↵
if(cur>s) return 0;↵
st.erase(st.begin());↵
if(st.size()==0) break;↵
auto it = st.upper_bound(s-cur);↵
if(it==st.begin()) continue;↵
st.erase(prev(it));↵
}↵
return r<=ride;↵
}↵
ll f(ll ride){↵
ll l = 0;↵
ll r = INT32_MAX;↵
while(l<=r){↵
ll mid = (l+r)>>1;↵
if(!pos(mid,ride)) l = mid+1;↵
else r = mid-1;↵
}↵
return ride*l;↵
}↵
int main(){↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
int n; cin>>n;↵
map<int,int>m;↵
for(int i=1; i<=n; i++){↵
int a; cin>>a;↵
m[a]++;↵
}↵
for(auto p : m) arr.push_back(p.second);↵
sort(arr.begin(),arr.end());↵
if(arr.size()==1){↵
cout<<arr.back();↵
return 0;↵
}↵
ll ans = INT64_MAX;↵
for(int i=(arr.size()/2+arr.size()%2); i<=arr.size(); i++){↵
ans = min(ans,f(i));↵
}↵
cout<<ans;↵
}↵
~~~~~↵
↵
https://mirror.codeforces.com/problemset/problem/1250/B↵
↵
this problem has no editorial.↵
i just iterated all possible r and calculate minimum s with binary search↵
↵
doing binary search, i greedily tried to take two teams at one ride if it's possible.↵
if s is fixed and current team has c member, i checked whether there's a team with maximum number of members d <= (s-c) ↵
if there's such team, two team can ride together, otherwise just take one time at this ride. ↵
↵
is it logically wrong? or implementation is wrong? need help!↵
(also i wanna know if there's a solution with complexity k^2 or faster , since my code is too slow ) ↵
↵
↵
↵
↵
↵
UDP: another version that doesn't use binary search and multiset yet produces same Wrong Answer.↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
typedef pair<int,int> pi;↵
vector<int>arr;↵
int pointer;↵
↵
bool pos(ll s,ll ride){↵
if(s<arr.back()) return 0;↵
deque<int>deq(arr.begin(),arr.end());↵
ll ret = 0;↵
while(deq.size()){↵
ret++;↵
int sz = deq.back();↵
deq.pop_back();↵
if(deq.size() && deq.front()+sz<=s){↵
deq.pop_front();↵
}↵
}↵
return ret<=ride;↵
}↵
ll f(ll ride){↵
while(pos(pointer,ride)) pointer--;↵
pointer++;↵
return ride*pointer;↵
}↵
int main(){↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
int n; cin>>n;↵
map<int,int>m;↵
for(int i=1; i<=n; i++){↵
int a; cin>>a;↵
m[a]++;↵
}↵
for(auto p : m) arr.push_back(p.second);↵
sort(arr.begin(),arr.end());↵
if(arr.size()==1){↵
cout<<arr.back();↵
return 0;↵
}↵
↵
pointer = n;↵
ll ans = INT64_MAX;↵
for(int i=(arr.size()/2+arr.size()%2); i<=arr.size(); i++){↵
ans = min(ans,f(i));↵
}↵
cout<<ans;↵
}↵
~~~~~↵
↵
