AcWing 1227. 分巧克力

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1227. 分巧克力原题链接中等

作者：

Daniel丶y , 2019-12-08 23:30:08 , 所有人可见 , 阅读 5148

27

15

题目链接： AcWing 1227 分巧克力

题意： 给定若干个矩形，从中切割出不少于$K$个边长相同的正方形，问正方形个数不少于$K$时，边长最大能达到多少

解题思路：

显然是一个二分答案的思路，题目中说了每个小朋友至少能分得一个$1\times 1$大小的正方形，所以边长最小为$1$，最大值可以设定一个足够大的数，比如题目中给的数据范围$10^5$，若当前选择的边长满足要求，则说明还有可能取更长的边长，当然也有可能不能取更长了，答案就是当前这个；若当前这个边长不能满足要求，则说明当前边长不可能是最终答案
满足要求在此题中的意思是至少能够分得$K$个当前选择边长的正方形

注意事项：

首先是选择二分模板，也就是看找要的点是在数轴的左端还是右端，上面分析中，我在此题所选择的性质是能够至少分得$K$个当前$mid$值为边长的正方形，画图如下：

如何判断是否满足这个性质？很容易就可以推出，若当前所取的边长为$mid$，对于一个矩形来说，只需要分别用它的长和宽整除这个$mid$，然后把结果相乘，就得到这个矩形能够分成多少个边长为$mid$的正方形了，把所有的矩形分割的结果相加，就得到总数，可以和$K$比较了

代码如下：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, k;  // 有n块巧克力，k个小朋友
int wid[N], len[N];  // 分别保存巧克力的长和宽

// 计算当正方形的边长为u时，总共能分得多少块巧克力
int get_sum(int u) {
  int sum = 0;
  for (int i = 0; i < n; i++) {
    // 要的就是整除
    sum += ((wid[i] / u) * (len[i] / u));
  }
  return sum;
}

int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &wid[i], &len[i]);
  }
  // 二分模板
  // 按照y总所分析的，我这里所取的性质是“当边长取mid时，能够分得k块巧克力”
  // 显然在一个数轴上，目标值的左侧（比目标值小的数）都是满足这个性质的，右边则不满足
  // 所以我们要找的值是满足这个性质的最右端
  // 如果当前取的mid满足这个性质，那么l有可能就是我们要找的目标值，所以用l = mid来更新
  // 综上所述，用以下模板
  int l = 0, r = N;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (get_sum(mid) >= k) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  printf("%d\n", l);
  return 0;
}

20 评论

a文 9个月前

左右边界划分的时候右边界为什么不能是n啊

#include <bits/stdc++.h>
using namespace std;
const int N= 1e5+5;
int n,m;
int w[N],len[N];
int dp(int u)//找到最小 
{
    int sum=0;
    for(int i=0;i<n;i++)
    sum+=((w[i]/u)*(len[i]/u));
    return sum;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>w[i]>>len[i];  
    }
    int l=0,r=n;//判断到n应该也行 
    while(l<r)
    {
        int mid=(l+r+1)/2;
        if(dp(mid)>=m)
        l=mid; 
        else
        r=mid-1;
    }
    cout<<l;
}

Daniel丶y 9个月前

$n$ 是巧克力块数，跟边长没关系。

a文 9个月前回复了 Daniel丶y 的评论

okkkkkkkk

陈叔健爱学习 2022-04-02 11:00

老哥，能不能用另一个模板做？？

陈叔健爱学习 2022-04-02 11:01

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long LL;
int h[N], w[N];
int n, k;

bool check (int mid) {
    LL res = 0;
    for (int i = 0; i < n; i ++) {
        res += (LL)(h[i] / mid) * (w[i] / mid);
        if (res < k) return true;
    }
    return false;
}

int main () {
  cin >> n >> k;
  for (int i =0; i < n; i ++) {
    cin >> h[i] >> w[i];
  }
  int l = 1;//最小是 1x1的巧克力 所以左边界为1
  int r = 1e5;//题目限制的最大范围
  while (l < r) {
      int mid = l + r  >> 1;
      if (check(mid)) {
          r = mid;
      }
      else {
          l = mid + 1 ;
      }
  }
  cout << l << endl;
  return 0;
}

一直WA

acgangster 2022-04-02 11:08 回复了陈叔健爱学习的评论

对啊对啊我也纳闷这个

acgangster 2022-04-02 11:08 回复了陈叔健爱学习的评论

check里应该是res < =k 但这样改也是WA

陈叔健爱学习 2022-04-02 11:23 回复了 acgangster 的评论

Daniel丶y 2022-04-03 21:22 回复了陈叔健爱学习的评论

不能，因为这两个二分模板最终落在的边界点，就是满足 check() 条件的。而且你的代码里，你可以思考一下， check() 里面，如果数据中第一个矩形特别小，那么 res 在运算第一个矩形的时候的结果也会特别小，就总是会直接返回 true 了。

陈叔健爱学习 2022-04-03 21:24 回复了 Daniel丶y 的评论

是的，我这几天想明白了，感谢！

Daniel丶y 2022-04-04 08:30 回复了陈叔健爱学习的评论

你硬要用也是可以用的其实，就是找 最小的不符合要求的点 ，这个点减 $1$ ，就是 最大的符合要求的点 了，但在思维上绕了一圈，所以还是建议用另一个模板。
代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long LL;
int h[N], w[N];
int n, k;

bool check (int mid) {
    LL res = 0;
    for (int i = 0; i < n; i ++) {
        res += (LL)(h[i] / mid) * (w[i] / mid);
    }
    return res < k;
}

int main () {
  cin >> n >> k;
  for (int i =0; i < n; i ++) {
    cin >> h[i] >> w[i];
  }
  int l = 1;
  int r = 1e5 + 1;
  while (l < r) {
      int mid = (l + r)  >> 1;
      if (check(mid)) {
          r = mid;
      }
      else {
          l = mid + 1;
      }
  }
  cout << l - 1 << endl;
  return 0;
}