ABC155 D pair 边界处理取整
2024-09-04 12:51:38
ABC155 D pair 取整坑点
思路
很常见的一道题,二分找答案,然后看这个答案排rank?,排rank?用二分继续找一遍二分套二分即可,就是边界比较烦,老年人写的心情烦躁
老年人被取整坑的几天。这题其实以前写过,以前被坑过,然后这次又被坑了一次,不愧是我。。。
1.ceil和floor一个是接近无穷大,另外一个是接近无穷小取
2.直接两个int除 是向0取整 int(-1/2)=-1 int(-4/3)=-1也就是负数的时候和人正常的向下取整逻辑不一样,逻辑上认为是向小了取,而事实是向0取
3.如果n>=m>0向上取整建议(n-1)/m+1
4.负数的时候推荐使用ceil 除非精度要求特别高 否则一般不会翻车
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define mkp make_pair
#define pii pair<int,int>
typedef long long ll;
const int maxn=2e5+5;
const int mod=1e9+7;
ll n,k,ling;
ll a[maxn];
bool check(ll x){
ll cnt=0;
for(int i=0;i<n;i++){
if(a[i]==0){
if(x>=0)cnt+=n-1;
continue;
}
else if(a[i]<0){
ll tmp=0;
if(x>=0)tmp=x/a[i];//a[i]*tmp<=x
else {
if(x%a[i]==0)tmp=x/a[i];
else tmp=x/a[i]+1;
}
cnt+=n-(lower_bound(a,a+n,tmp)-a);
}
else if(a[i]>0){
ll tmp=0;
if(x>=0)tmp=x/a[i];
else{
if(x%a[i]==0)tmp=x/a[i];
else tmp=x/a[i]-1;
}
cnt+=upper_bound(a,a+n,tmp)-a;
}
if(a[i]*a[i]<=x)cnt--;
//cout<<cnt<<endl;
}
return cnt/2>=k;
}
int main(){
scanf("%lld%lld",&n,&k);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
}
sort(a,a+n);
ll l=-1e18,r=1e18,ans=0;
while(l<=r){
ll mid=(l+r)/2;
if(check(mid))r=mid-1,ans=mid;
else l=mid+1;
}
//check(-6);
cout<<ans<<endl;
}
最新文章
- MongoDB学习笔记~关于官方驱动集成IQueryable之后的一些事
- UICollectionView 自定义组头组尾的XIB方法
- html基础二
- linux命令学习(1):grep 命令
- 2、分布式文件系统---HDFS
- Android使用Dom解析xml
- 【转】CoreData以及MagicalRecord (一)
- 微信公众平台创建自定义菜单的PHP代码
- 【Unity3D】Unity3D开发《我的世界》之七、番外篇
- CHENGDU3-Restful API 接口规范、django-rest-framework框架
- js实现sleep
- ]remove-duplicates-from-sorted-list-ii (删除)
- Python自动化运维工具-Fabric部署及使用总结
- MySQL 5.7 的SSL加密方法
- PHP多进程非阻塞模式下结合原生Mysql与单进程效率测试对比
- templates的语法
- VB API判断数组为空
- 在liferay中如何使用Ajax的请求
- 在微信开发中如果WeixinJSBridge.call(&#39;closeWindow&#39;);关闭窗口无效!
- DateUtils 通用类
热门文章
- JS高阶编程技巧--compose函数
- ASP .NET CORE 源码地址
- 基于Struts2开发校园二手购物商城源码
- CSS中的vertical-align属性
- opencv —— contourArea、arcLength 计算轮廓面积与长度
- Jetty配置虚拟目录,实现把web项目发布到自定义目录,指定指定上下文访问;jetty编码修改
- 在 Nest.js 中使用 MongoDB 与 TypeORM
- linuxWeb环境安装——小皮面板不错的面板
- docker - apt-get更换国内源解决Dockerfile构建速度过慢
- #AcWing系列课程Level-2笔记——1. 快速排序算法