博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 8208 矩形分割 【二分】【北大ACM/ICPC竞赛训练】
阅读量:5326 次
发布时间:2019-06-14

本文共 1432 字,大约阅读时间需要 4 分钟。

 要使两边面积之差最小且保证小矩形直线左边面积大于等于右边面积,在此基础上使大矩形在直线左边的面积尽量大。

想了想后我把这道题分为两步解决,首先找到面积之差的最小值;然后想到一个范围内划直线都是这个最小值,在这个范围内找到最右边的(即保证大矩形左边的面积最大)。

第一次二分算面积之差最小值,square(k)返回x=k这条直线左边小矩形的面积,s是所有小矩形的面积;若square(k)>=s-square(k),那面积差最小就在k的左边(包括k),不然就在k+1右边找。

第二次二分的本质是左右矩形的差,首先保证直线左边小矩形面积大于等于小矩形右边面积,然后如果cha>mincha,那就在k左边找;不然的话cha=mincha(因为不会更小了)那就往k右边找

1 #include
2 #define ll long long 3 using namespace std; 4 5 long long s,minc=1000000000000; 6 int l[10005],t[10005],w[10005],h[10005],n; 7 long long square(int k){
//划出x=k这条直线,小矩形在直线左边的面积 8 long long ans=0; 9 for(int i=1;i<=n;i++){10 if(l[i]+w[i]<=k) ans+=(ll)w[i]*h[i];11 else if( l[i]
>r>>n;18 for(int i=1;i<=n;i++) {19 cin>>l[i]>>t[i]>>w[i]>>h[i];20 s+=(ll)w[i]*h[i];21 }22 23 int start=0,end=r,mid,ans;24 while(end>=start){25 mid = (start+end)/2;26 long long sq=square(mid);27 //cout<
<<" "<
<<" "<
<<" "<
<
=s-sq){30 minc=sq*2-s;31 end=mid-1;32 }33 else start=mid+1;34 }35 36 start=0,end=r;37 while(end>=start){38 mid = (start+end)/2;39 long long sq=square(mid),cha=sq*2-s;40 //cout<
<<" "<
<<" "<
<<" "<
<
=s-sq ){ //直线左边小矩形面积大于右边的 42 if(cha>minc) end=mid-1;43 else ans=mid,start=mid+1;44 }45 else start=mid+1;46 }47 48 //cout<
<

 

转载于:https://www.cnblogs.com/ZhenghangHu/p/9357333.html

你可能感兴趣的文章
mysql5.x升级至mysql5.7后导入之前数据库date出错的解决方法!
查看>>
对闭包的理解
查看>>
练习10-1 使用递归函数计算1到n之和(10 分
查看>>
Oracle MySQL yaSSL 不明细节缓冲区溢出漏洞2
查看>>
windows编程ASCII问题
查看>>
.net webService代理类
查看>>
Code Snippet
查看>>
Node.js Express项目搭建
查看>>
zoj 1232 Adventure of Super Mario
查看>>
Oracle 序列的应用
查看>>
1201 网页基础--JavaScript(DOM)
查看>>
组合数学 UVa 11538 Chess Queen
查看>>
oracle job
查看>>
Redis常用命令
查看>>
XML学习笔记(二)-- DTD格式规范
查看>>
IOS开发学习笔记026-UITableView的使用
查看>>
[转载]电脑小绝技
查看>>
windos系统定时执行批处理文件(bat文件)
查看>>
thinkphp如何实现伪静态
查看>>
BZOJ 2243: [SDOI2011]染色( 树链剖分 )
查看>>