链接:https://atcoder.jp/contests/abc143/tasks/abc143_f

题解:开两个数组,其中一个arr用来保存每个元素出现的次数,同时再开一个数组crr用来保存出现次数等于其下标的个数,然后对crr求前缀和,crr就变成了出现次数维护小于其小标的总个数。

根据题意:每次取k个,k个元素各不相同,问最多可以取多少次,假设可以取 x次,为了保证每个元素不相同,那么每个元素出现的次数最多为x次,并且总个数为k*x,因此这里可以用二分来判断。

AC代码:

//crr[i]指的是当前每个元素出现的次数小于i的总个数.
//取k个,一共取mid次,所以要求就是当前区间总个数应该大于等于mid*k。
//由于区间crr维护的是当前出现次数小于下标的元素个数,所以每次取都不会取得相同的元素。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3E5+;
ll arr[N];
ll crr[N];
int main(){
int n;
cin>>n;
for(int i=;i<=n;i++){
ll x;
cin>>x;
arr[x]++;
crr[arr[x]]++;//这样可以让crr维护出现次数大于等于其下标的元素的个数。秒。。
}
for(int i=;i<=n;i++) crr[i]+=crr[i-];
for(int k=;k<=n;k++){
ll ans=;
ll left=,right=n;
while(left<=right){
ll mid=(left+right)/;
if(k*mid<=crr[mid]){
left=mid+;
ans=max(ans,mid);
}
else{
right=mid-;
}
}
cout<<ans<<endl;
}
return ;
}

最新文章

  1. alphaBlend
  2. VS2010+C#+在新建类或接口时在文件开头自动生成作者和日期等备注
  3. bootstrap实现嵌入的button
  4. IEnumerable 遍历用法
  5. 【XLL API 函数】xlGetHwnd
  6. SQL语句创建数据库,SQL语句删除数据库,SQL语句创建表,SQL语句删除表,SQL语句添加约束,SQL语句删除约束
  7. C++标准转换运算符 --四种
  8. c#中serialPort1_DataReceived串口接收事件处理
  9. Qt widget--杭州小笼包
  10. 你真的了解mysql的varchar字段的长度有多少吗?
  11. Redis数据类型之Hash(二)
  12. 计蒜客模拟赛D1T1 蒜头君打地鼠:矩阵旋转+二维前缀和
  13. HTML学习笔记 域元素(form表单、textarea文本域、fieldset域集合、input使用) 案例 第四节 (原创)
  14. iOS学习——输入验证码界面封装
  15. [Harbor]Harbor简要介绍
  16. Linux 设置系统时间和时区2.Ubuntu
  17. ARTS打卡计划第一周-Tips-ControllerAdvice的使用
  18. Kafka中bootstrap-server、broker-list和zookeeper的区别
  19. offsetWidth与clientWidth 区别
  20. Elasticsearch 节点角色说明

热门文章

  1. hdu2066多源最短路
  2. editplus软件使用技巧
  3. H3C路由器地址池租期时间H3CMSR830-6BHI-WiNet
  4. w3cshool -- 排列组合去重算法挑战
  5. arcgis server建完站点之后修改默认6080端口号
  6. return console.log()结果为undefined现象的解答
  7. Spring中的设计模式:模板模式
  8. Spring中的设计模式:工厂方法模式
  9. Js闭包练习2020031801
  10. IDEA+Mybatis-generator代码生成工具