来自M78的光之文轩 2022-11-05 20:29 采纳率: 92%
浏览 86
已结题

NOI的1.11编程基础之二分查找的03:矩形分割 代码找不到错误

NOI的1.11编程基础之二分查找的03:矩形分割 代码找不到错误
原题在http://noi.openjudge.cn/ch0111/03/
下面是我自己的代码


#include<iostream>
using namespace std;
typedef struct{
        int x;          //用结构体Nb存放小矩形,坐标(x,y)
        int y;
        int len_x;
        int len_y;
    }Nb;
long long get_size(int left,int right,Nb CNb[],int N){   //输入区间,获取从左边到右边所有小矩形的面积 
    long long size=0;
    int i;
    if(left>=right) return 0;
    for(i=0;i<N;i++){
        if(CNb[i].x+CNb[i].len_x<=left || CNb[i].x>=right) continue;
        else if(CNb[i].x>=left && CNb[i].x+CNb[i].len_x<=right) size+=CNb[i].len_y*CNb[i].len_x;
        else if(CNb[i].x<left && CNb[i].x+CNb[i].len_x<=right) size+=CNb[i].len_y*(CNb[i].len_x+CNb[i].x-left);
        else if(CNb[i].x<left && CNb[i].x+CNb[i].len_x>right) size+=CNb[i].len_y*(right-left);
        else size+=CNb[i].len_y*(right-CNb[i].x);
    }
    return size;
}
int main(){
    int R,N;
    cin>>R>>N;
    Nb CNb[10002];   //用CNb来存储,每次输入的小矩形 
    int i,l;
    for(i=0;i<N;i++) cin>>CNb[i].x>>CNb[i].y>>CNb[i].len_x>>CNb[i].len_y;   //输入小矩形 
    long long size_left,size_right; 
    int left=0,right=R,mid;
    if(get_size(0,R,CNb,N)==0){cout<<R; return 0;}
    while(1){
        mid=(left+right)/2;
        size_left = get_size(0,mid,CNb,N);
        size_right=get_size(mid,R,CNb,N);
        if(size_left == size_right){   //如果左右面积相等  
            for(l=mid+1; get_size(0,l,CNb,N) == get_size(l,R,CNb,N); l++){if(l>R) break;}  //把分割线逐渐右移,直到左边面积!=右边 
            cout<<l-1;
            return 0;
        }
        else if(size_left>size_right && get_size(0,mid-1,CNb,N)<get_size(mid-1,R,CNb,N)){ //如果左边大于右边并且分割线左移1格之后左边小于右边,mid即为分割线 
            cout<<mid;
            return 0;
        }
        else if(size_left>size_right) right=mid; //左边小于右边
        else left=mid;  //右边小于左边
    }
}
  • 写回答

2条回答 默认 最新

  • CSDN专家-link 2022-11-05 20:41
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 11月7日
  • 已采纳回答 11月7日
  • 修改了问题 11月7日
  • 修改了问题 11月7日
  • 展开全部

悬赏问题

  • ¥66 定制开发肯德基自动化网站下单软件
  • ¥20 vscode虚拟环境依赖包未安装
  • ¥15 odoo17关于owl开发js代码问题
  • ¥15 光纤中多普勒频移公式的推导
  • ¥15 怎么制作一个人脸识别门禁系统
  • ¥20 大华dss监控平台网络关闭登不进去
  • ¥15 请使用蚁群算法解决下列问题,并给出我完整的代码
  • ¥20 关于php录入完成后,批量更新数据库
  • ¥15 请教往复密封润滑问题
  • ¥15 cocos creator发布ios包