P1678 烦恼的高考志愿(二分)
2024-10-19 04:28:19
emmmm,我感觉我在解题的过程中还是有点吃亏的,因为,我知道是二分,只是大概知道怎么分,没有管这道到底是需要怎样的二分。然后在题上卡了很久。
思路:要找到填报学校的录取线x和自己的分数y的绝对值最小,其实,我们直接找到第一个大于它的数字和最后一个小于它数字比较一下就可以了。当然,进行排序后。
这两个值是相邻的,那就直接利用二分进行查找第一个大于它的数即可!还有一个小细节就是,要考虑找不到第一个大于它的数的情况。
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+;
int a[maxn], b[maxn], n, m;
int l, r, mid, ans, sum; int main(){
cin>>n>>m;
for(int i=;i<=n;++i)cin>>a[i];
for(int i=;i<=m;++i)cin>>b[i];
sort(a+, a+n+);
//找到第一个比它大的
for(int i=;i<=m;++i){
l=; r=n;
while(l<r){
mid=(l+r)>>;
if(a[mid]>=b[i]){r=mid;} //将边界左移动
else l=mid+;
}
if(b[i]<a[]){ //找不到第一个小于它的数
sum+=a[]-b[i];
}else{
sum+=min(abs(a[l-]-b[i]), abs(a[l]-b[i])); //比较第一个大于,最后一个小于的绝对值的大小,取小的
}
}
cout<<sum<<endl;
}
最新文章
- python中文编码问题
- 使用功能强大的插件FastReport.Net打印报表实例
- JS-011-颜色进制转换(RGB转16进制;16进制转RGB)
- [AX]AX2012 Number sequence framework :(三)再谈Number sequence
- jQuery 基础
- IOS 开展 分别制定了iphone 和 ipad 好? 或开发一个 Universal好?
- CSS hack 如何区分所有IE浏览器和非IE浏览器
- Android(Java) 字符串的常用操作,获取指定字符出现的次数,根据指定字符截取字符串
- 禁止Centos7系统yum自动下载更新
- JS获取键盘事件
- Thread.join(), CountDownLatch、CyclicBarrier和 Semaphore区别,联系及应用
- java0422 wen 集合框架
- MemcachedUI-一款基于.NET MVC编写的Memcached监控软件
- 缓存算法(FIFO 、LRU、LFU三种算法的区别)
- Looper loop
- Unity shader学习之Forward Rendering Path
- HDU-6336-构造
- (转)mysql升级5.5.20时遇到的问题:1548-Cannot load from mysql.proc. The table is probably corrupted
- oracle中insert 多条数据方法
- Useful Field of View (UFOV)
热门文章
- 浅谈spring中AOP以及spring中AOP的注解方式
- 汇编语言--微机CPU的指令系统(五)(字符串操作指令)
- shell 备份 source code
- html5对于seo有哪些优势
- angular ng-click防止重复提交
- 向后台提交数据:通过form表单提交数据需刷新网页 但通过Ajax提交数据不用刷新网页可通过原生态Ajax或jqueryAjax。Ajax代码部分
- concrrent类下 BlockingDeque 下 自己实现代码编写
- Android为TV端助力 很详细的序列化过程Parcelable
- Android为TV端助力 fragment 的用法以及与activity的交互和保存数据的方法,包括屏幕切换(转载)!
- Java面试题总结(不定期更新)