分巧克力刷题笔记

2024-03-05 05:20

文章标签 笔记刷题巧克力

本文主要是介绍分巧克力刷题笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*
分巧克力解题思路
二分
直接检查看答案是否符合题目条件
对于一块边长分别为x 和y的巧克力\\
假设我们输入检查的数为k
其能分割成的 k*k 的巧克力的块数为
(x/k)*(y/k)
因为c++里面的除法是下取整的所以我们不用考虑奇偶数是否能整除

将每一块巧克力能分成的k*k的巧克力块数加上计数器
一旦计数器超过了孩子数我们就返回true;
如果check 不通过的话可能是分的太大了
所以答案小于mid
于是我们让r=mid-1
如果check通过
则答案>=mid 所以我们让l=mid
重点讨论边界情况
例如案例中
2 10
6 5
5 6

输出2
当 l指向2 r指向3
mid=(l+r)>>1;的话 mid 是2
此时check可以通过
但是l=2,r=3;
如果还是l=mid=2则陷入死循环
于是我们让mid=(l+r+1)>>1
让其进行上取整
则 mid=3;
check不通过
此时 r=mid-1=l；
退出循环

输出l或者r即可

*/

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+10;
struct node{
   int x;
   int y;
}a[N];
int n,k;
bool check(int p){
   int cnt=0;
   bool flag=false;
//   cout<<"p is "<<p<<endl;
   for(int i=0;i<n;i++){
       cnt=cnt+(a[i].x /p)*(a[i].y /p);
       //cout <<cnt<<endl;
       if(cnt>=k){
           flag= true;
           break;
       }

   }
   return flag;
}
int main(){
   cin>>n>>k;
   int r=0;
   for(int i=0;i<n;i++){
       cin>>a[i].x >>a[i].y;
       if(a[i].x >a[i].y ){
           if(a[i].x >r){
               r=a[i].x ;
           }
       }else{
           if(a[i].y >r){
               r=a[i].y ;
           }
       }
   }
//   cout<<r<<endl;
   int l=0;
   while(l<r){
       int mid=(l+r+1)>>1;
       //cout<<mid<<endl;
       if(check(mid)){
           l=mid;
       }else{
           r=mid-1;
       }
       //cout<<"l is"<<l<<endl<<"r is "<<r<<endl;
   }
   cout <<l;
   return 0;
}