【洛谷P1978】 集合
2024-08-30 09:05:24
集合
显然,我们是要把数据先排序的,
然后从大到小枚举每个数,看是否能选上,
能选就选,不能拉倒
若能,二分查找a[i]/k,若查找成功,ans++
将a[i]/k标记为不能选择
最后输出答案即可
(从小到大枚举会爆long long)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 100010
#define int long long
int n,k,a[N],ans,Maxx;
bool not_ok[N];
#undef int
int main()
#define int long long
{
scanf("%lld%lld",&n,&k);
for(int i=;i<=n;i++)
scanf("%lld",&a[i]);
sort(a+,a++n);
for(int i=n;i>=;i--)
if(!not_ok[i]){
ans++;
if(a[i]%k!=) continue;
int l=,r=i-;
while(l<r){
int mid=(l+r)>>;
if(a[mid]>=a[i]/k) r=mid;
else l=mid+;
}
if(a[l]==a[i]/k) not_ok[l]=;
}
printf("%lld\n",ans);
return ;
}
最新文章
- xib和storyBoard哪些事之UIimage和按钮注意事项
- Java并发之死锁实例
- 增量式PID简单翻板角度控制
- 左侧导航栏复制粘贴保存html即可
- Nginx反向代理 负载均衡
- JavaScript的事件对象_事件流
- Zendstudio 9.0.2 安装Aptana3 并且配置 jQuery
- Ubuntu 14.04 eclipse 提示框背景色更改
- “layout_”下划线开头的属性
- 功率和dB的关系
- SAX解析xml浅析
- HTML <;button>;标签
- Java Trie字典树,前缀树
- MySql解除安全模式:Error Code: 1175. You are using safe update mode and you tried to update a table without a WHERE that uses a KEY column.
- Docker: dockerfile常用关键字
- 最小生成树Prim算法和Kruskal算法
- Storm消息可靠机制
- Instrumentation类——Android自动化测试学习历程
- 四则运算安卓版ver.mk2
- [Module] 08 - MVP by Mosby