咕噜小盒 2023-03-28 17:51 采纳率: 25%
浏览 21
已结题

二分算法的处理,不知道哪里有问题

这个是题目:

img


这个是我写的代码:
我用的是左闭右闭的方式
且是用向左取整

#include<stdio.h>
#include<stdlib.h> 
int n;   //n为巧克力数量
int check(int d,int k,int *a,int *b)
{
    int i,num=0;
    for(i=0;i<n;i++)
       {
           num=num+(a[i]/d)*(b[i]/d) ;      //总长/小长==数量 
        } 
    if(num>=k)         //说明够分 ,这个不太明白==,但是以后都这样写 
      return 1;
    else
      return 0;        //这是不够分的 
}
int main()
{
    int k,i=0,l,r,min,mid;//n为巧克力数量,k为朋友数量 
    scanf("%d%d",&n,&k);
    int a[k],b[k];//分别表示长和宽 
    r=1; 
    while(i<n)
       {
           scanf("%d%d",&a[i],&b[i]);
        i++; 
       min=a[i]>b[i]?b[i]:a[i];
        if(min>r)
          {
              r=min;
              }    
       }
    l=1;
    while(l<=r)
      {
          mid=(l+r)>>1 ;    //我一般都是使用向左取整
        if(check(mid,k,a,b)==1) 
          {
              l=mid+1;
          }
        else
           {
               r=mid-1;
           }
      }
    printf("%d",l);
    return 0;
    
}

但是我运行出来的答案是这样的:

img

我看了一下参考代码
是在最后打印那里不太一样,参考代码是这样的:printf("%d",l-1);
我一直理解不了为什么要减一呢?

  • 写回答

2条回答 默认 最新

  • 请叫我问哥 Python领域新星创作者 2023-03-28 18:10
    关注

    因为你在check为真后,l=mid+1,所以最后找到的l指向的是第一个check为假的值,所以要回退一位

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 4月13日
  • 已采纳回答 4月5日
  • 创建了问题 3月28日

悬赏问题

  • ¥15 table表格有一列是固定列 滑动到最下面时 固定的那一列有几行没显示出来
  • ¥20 单细胞数据注释时报错
  • ¥20 dify工作流分析sql查询结果
  • ¥15 vscode编译ros找不到头文件,cmake.list文件出问题,如何解决?(语言-c++|操作系统-linux)
  • ¥15 通过AT指令控制esp8266发送信息
  • ¥15 有哪些AI工具提供可以通过代码上传EXCEL文件的API接口,并反馈分析结果
  • ¥15 二维装箱算法、矩形排列算法(相关搜索:二维装箱)
  • ¥20 nrf2401上电之后执行特定任务概率性一直处于最大重发状态
  • ¥15 二分图中俩集合中节点数与连边概率的关系
  • ¥20 wordpress如何限制ip访问频率