B. Power Walking
题目大意：
有n个物品要分给k个人，第i种物品的种类是ai。每个人的力量值是他所拥有的物品的种类数量。问对于看属于1到n的每一种人数，所有人的最小力量值和是多少。
思路和代码：
举个栗子：1 1 1 2 2 2 3
因为最后物品数等于人数，所以最后输出的答案肯定是n。倒过来想这个过程，分给n-1个的时候为了使多出来的那个物品对总体和的影响最小，应该选择数量多的那一类的物品。
7 1 1 1 2 2 2 3 ==>7
6 (1 1) 1 2 2 2 3 ==>6
5 (1 1 1) 2 2 2 3 ==>5
4 (1 1 1)(2 2) 2 3 ==>4
3 (1 1 1)(2 2 2) 3 ==>3
2 (1 1 1 2 2 2)3 ==>3
1 (1 1 1 2 2 2 3) == >3
将【1 1 1 2 2 2 3】按照每种的数量放到新数组b里降序排序得到【3 3 1】。
bi > 1和bi == 1分情况讨论，具体看代码。
bool cmp(ll u , ll v){
return u > v ;
}
void solve(){
cin >> n ;
vct<ll> a(n + 1 , 0) ;
rep(i , 1 , n) cin >> a[i] ;
map<ll , ll> mp ;
vct<ll> num ;
rep(i , 1 , n){
if(!mp[a[i]]) num.pb(a[i]) ;
mp[a[i]] ++ ;
}
vct<ll> b ;
rep(i , 0 , num.size() - 1)b.pb(mp[num[i]]) ;//种数放到b里排序
sort(b.begin() , b.end() , cmp) ;
ll ans = n , tps = num.size() ;
stack<ll> res ;
rep(i , 0 , b.size() - 1){
if(b[i] == 1){
res.push(max(tps , ans)) ;
continue ;
}
while(b[i]){
res.push(max(tps , ans)) ;
ans -- ;b[i] -- ;
}
}
while(res.size()){
cout << res.top() << " " ;
res.pop() ;
}
cout << "\n" ;
}//code_by_tyrii
/*
7
2 2 2 1 4 5 1
*/
但是这种方法其实很笨。
我做这题想到人数等于n时答案是ans=n就从后往前去考虑了（受到之前做的一道题的影响，就反过来想了）
正过来想，当人数小于等于种数时，ans=种数。当人数大于种数时，就不得不拿出一个到新的人身上，ans++。（就很简单orz）
void solve2(){
ll n ; cin >> n ;
vct<ll> a(n , 0) ;
map<ll , ll> mp ;
rep(i , 0 , n - 1){
cin >> a[i] ;
mp[a[i]] ++ ;
}
rep(i , 1 , mp.size()) cout << mp.size() << " " ;
rep(i , mp.size() + 1 , n) cout << i << " " ;
cout << "\n" ;
}
小结：
一般做题目还是优先正过来思考，正过来不行再去思考反过来的做法。不能因为第n个ans固定就直接反过来做，我这题就是这样而绕了远路，忽视了从正面切入，从而失去了使用简单解法的机会。
以后还是得思考全面，正面思路优先。
C. Great Sequence
题目大意：
一个偶数个数序列，若在其中前二分之一的每一个位置i，ai都能找到另外一个aj，使得ai*k=aj,则满足条件。（大概就这么个意思，可能有偏差）
思路和代码：
我一开始想的是，做multiset，然后去找ai*k，若找不到则要增加，反之删除j的迭代器。
void solve(){
ll ans = 0 ;
cin >> n >> k ;
vct<ll> a(n , 0) ;
multiset<ll> st ;
rep(i , 0 , n - 1) cin >> a[i] ;
rep(i , 0 , n - 1) st.insert(a[i]) ;
for(auto it = st.begin() ; it != st.end() ; it ++ ){
auto itj = lwbd(st.begin() , st.end() , (*it) * k) ;
if(*itj == (*it) * k && (it != st.end())){
//st.erase(it) ;删除当前迭代器会有很大问题，不能继续遍历set
st.erase(itj) ;
}else ans ++ ;
}
cout << ans << "\n" ;
}//code_by_tyrii
但是这拿了RE，不太清楚为什么=_=
后来发现是可以用set加map做的。set存元素，map存对应元素的数量（不存在的数量就是0）思路和上面是一样的。
void solve(){
cin >> n >> k ;
map<ll , ll> num ;
set<ll> st ;
rep(i , 1 , n){
ll tmp ; cin >> tmp ;
num[tmp] ++ ;
st.insert(tmp) ;
}
ll ans = 0 ;
for(auto i : st){
if(num[i] > num[i * k]){
ans += num[i] - num[i * k] ;
num[i * k] = 0 ;
}else{
num[i * k] -= num[i] ;
}
}
cout << ans << "\n" ;
}
小结：
这题拿来想到了multiset的做法，O(logn)的复杂度又可以接受，我就直接做了。没有想到multiset的细节问题。需要补一下multiset的知识。
当然，以后做题找到了复杂度合适的解法也不能直接开做，要再多想一步。