2022-05-25每日刷题打卡
代码源——每日一题
全部相等 - 题目 - Daimayuan Online Judge
给定长度为 n 的数组 {A}。
派派非常喜欢 所有元素出现频率相同 的数组，但这样的数组却不常有。派派很伤心 (;′??Д??`)。不过聪明的你，发现总能从 {A} 中挑选一个子序列满足上述条件。问此子序列最长为多长？
数据规模
1≤n≤2×105
Ai∈[1,109]
输入格式
输入包含两行，第一行有一个整数 n，表示 {A} 的大小。
接下来一行包含 n 个用空格分隔的整数，依次表示 A1,A2,?,An。
输出格式
输出答案。
样例 1 输入
6
1 3 2 1 4 2
样例 1 输出
4
解释：
[1,2,1,2] 满足条件且最长。
问题解析
这题说的是要我们找一个子序列，而且只要子序列内的元素出现频率相等即可，那我们也不用考虑这些元素的先后顺序什么的了。
先把每个数的出现次数记录下来存入数组中并排序，比如样例就会变成：1、1、2、2。
此时问题就变成了：从我们的数组中选出一个数，让（大于等于这个数的个数*这个数）最大即可。
我们从前往后一个个推，因为我们按照升序排序，可以保证后面的数肯定比当前数大，我们拿样例举例来说：
第一个数是1，后面有三个大于等于它的数，加上自己，一共是四个，那么这个子序列的长度就可以是1*4=4。
第二个数是1，后面有两个大于等于它的数，加上自己，一共是三个，那么这个子序列的长度就可以是1*3=3。
第三个数是2，后面有一个大于等于它的数，加上自己，一共是二个，那么这个子序列的长度就可以是2*2=4。
第四个数是2，后面有零个大于等于它的数，加上自己，一共是一个，那么这个子序列的长度就可以是2*1=2。
那么子序列最长是4，可以是【1，2，1，2】，也可以是【1，2，3，4】
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
sort(v.begin(), v.end());
v.push_back(-1);
int ans = 1;
vector<int>cnt;
for (int i = 1; i <= n; i++)
{
if (v[i - 1] != v[i])
{
cnt.push_back(ans);
ans = 1;
}
else ans++;
}
sort(cnt.begin(), cnt.end());
n = cnt.size();
int res = 0;
for (int i = 0; i < n; i++)
{
res = max(res, cnt[i] * (n - i));
}
cout << res << endl;
return 0;
}
