网站优化软件开发,wordpress delete_option,领航 网站设计,上海尤安建筑设计股份有限公司/* 分巧克力 解题思路 二分 直接检查看答案是否符合题目条件 对于一块边长分别为x 和y的巧克力\\ 假设我们输入检查的数为k 其能分割成的 k*k 的巧克力的块数为 (x/k)*(y/k) 因为c里面的除法是下取整的所以我们不用考虑奇偶数 是否能整除
将每一块巧克力能分成的k*k的巧克力… /* 分巧克力 解题思路 二分 直接检查看答案是否符合题目条件 对于一块边长分别为x 和y的巧克力\\ 假设我们输入检查的数为k 其能分割成的 k*k 的巧克力的块数为 (x/k)*(y/k) 因为c里面的除法是下取整的所以我们不用考虑奇偶数 是否能整除
将每一块巧克力能分成的k*k的巧克力块数加上计数器 一旦计数器超过了孩子数 我们就返回true; 如果check 不通过的话 可能是分的太大了 所以答案小于mid 于是我们让rmid-1 如果check通过 则答案mid 所以我们让lmid 重点 讨论边界情况 例如案例中 2 10 6 5 5 6
输出2 当 l指向2 r指向3 mid(lr)1;的话 mid 是2 此时check可以通过 但是l2,r3; 如果还是lmid2则陷入死循环 于是 我们让mid(lr1)1 让其进行上取整 则 mid3; check不通过 此时 rmid-1l 退出循环 输出l或者r即可 */
代码
#includeiostream #includealgorithm #includecstdio #includecstring using namespace std; const int N1e510; struct node{ int x; int y; }a[N]; int n,k; bool check(int p){ int cnt0; bool flagfalse; // coutp is pendl; for(int i0;in;i){ cntcnt(a[i].x /p)*(a[i].y /p); //cout cntendl; if(cntk){ flag true; break; } } return flag; } int main(){ cinnk; int r0; for(int i0;in;i){ cina[i].x a[i].y; if(a[i].x a[i].y ){ if(a[i].x r){ ra[i].x ; } }else{ if(a[i].y r){ ra[i].y ; } } } // coutrendl; int l0; while(lr){ int mid(lr1)1; //coutmidendl; if(check(mid)){ lmid; }else{ rmid-1; } //coutl islendlr is rendl; } cout l; return 0; }
