来自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日
  • 展开全部

悬赏问题

  • ¥15 网络科学导论,网络控制
  • ¥100 安卓tv程序连接SQLSERVER2008问题
  • ¥15 利用Sentinel-2和Landsat8做一个水库的长时序NDVI的对比,为什么Snetinel-2计算的结果最小值特别小,而Lansat8就很平均
  • ¥15 metadata提取的PDF元数据,如何转换为一个Excel
  • ¥15 关于arduino编程toCharArray()函数的使用
  • ¥100 vc++混合CEF采用CLR方式编译报错
  • ¥15 coze 的插件输入飞书多维表格 app_token 后一直显示错误,如何解决?
  • ¥15 vite+vue3+plyr播放本地public文件夹下视频无法加载
  • ¥15 c#逐行读取txt文本,但是每一行里面数据之间空格数量不同
  • ¥50 如何openEuler 22.03上安装配置drbd