【离散化+枚举】代码源每日一题div2 全部相等

偏执的太偏执、 2024-03-16 18:44 45阅读 0赞

[全部相等 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![d43aef2e5aab4636aa548b58df18726d.png][]

思路：

首先，子序列最长，想到了DP，但是子序列DP，D不出来，所以要放弃想法

不难发现，这道题和顺序没有关系，所以可以说，它不是严格意义上的“子序列”

因为每个元素的出现次数相同，因此我们可以去**枚举**每个元素的出现次数，然后算贡献

贡献就是次数\*(出现次数大于这个次数的个数)

那么后者怎么算呢

可以考虑笨笨的线段树，但是事实上一个map的后缀和就能解决问题，这是很常见的trick

但是范围是1e9，怎么办呢？数列一共就不长，离散化一下即可

当值域太大时，考虑离散化

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    using i64 = long long;
    
    const int mxn=2e5+10;
    
    map<int,int> mp,mp2;
    
    int N,idx=0;
    int a[mxn];
    int mp3[mxn];
    
    int S(int x){
    	if(mp2.count(x)) return mp2[x];
    	return mp2[x]=++idx;
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=1;i<=N;i++){
    		a[i]=S(a[i]);
    		mp[a[i]]++;
    	}
    	//for(int i=1;i<=N;i++) cout<<a[i]<<" \n"[i==N];
    	for(auto it:mp) mp3[it.second]++;
    	for(int i=N;i>=1;i--) mp3[i]+=mp3[i+1];
    	int ans=0;
    	for(int c=1;c<=N;c++){
    		ans=max(ans,c*mp3[c]);
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/925
[d43aef2e5aab4636aa548b58df18726d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/eba7719bdf5f426e90f358d1d0258ac3.png