C4n 2022-01-01 13:45 采纳率: 80%
浏览 81
已结题

蓝桥杯 分巧克力 这样做为什么不行啊(语言-c++)

题目描述

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力,其中第i块是H[i] x W[i]的方格组成的长方形。
为了公平起见,小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:
(1) 形状是正方形,边长是整数
(2) 大小相同
例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。

当然小朋友们都希望得到的巧克力尽可能大,你能帮小明计算出最大的边长是多少么?

输入

第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数H[i]和W[i]。(1 <= H[i], W[i]<= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。

输出

输出切出的正方形巧克力最大可能的边长。

样例输入

2 10
6 5
5 6

样例输出

2

#include<bits/stdc++.h>
using namespace std;
int N,K;
int H[100000],W[100000];
long long sum; 
bool check(int d)
{
    if(K<=sum/(d*d))    return true;
    else            return false;
}
main()
{
    cin>>N>>K;
    for(int i=1;i<=N;i++)
    {
        cin>>H[i]>>W[i];
        sum+=H[i]*W[i];
    }
    int l(1),r(100000);
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid))  l=mid+1;
        else            r=mid;
    }
    cout<<l-1;
}

这样使用样例输入能输出样例输出结果,但是在蓝桥杯官网上面就检测不通过

  • 写回答

1条回答 默认 最新

  • 神仙别闹 2022-01-01 14:06
    关注
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int n,k;
    const int maxn = 100100;
    const int INF = 0x3f3f3f3f;
    int w[maxn],h[maxn];
    int Divide(int ww,int hh,int l){
        int res = ww/l;
        res *=  hh/l;
        return res;
    }
    bool check(int l){
        int res = 0;
        for(int i = 1;i <= n;i++)
            res += Divide(w[i],h[i],l);
        return res >= k;
    }
    void solve(){
        int l = 1,r = INF;
        while(l < r){
            int mid = (l+r)/2;
            if(check(mid)) l = mid+1;
            else r = mid;
        } 
        cout << l - 1<< endl;
    }
    int main(){
        scanf("%d%d",&n,&k);
        for(int i = 1;i <= n;i++) scanf("%d%d",h+i,w+i);
        solve();
        return 0;
    } 
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 4月19日
  • 已采纳回答 4月19日
  • 创建了问题 1月1日

悬赏问题

  • ¥15 广告联盟的兜底广告是什么意思
  • ¥15 如何证明高斯噪声的包络公式
  • ¥150 寻找王者荣耀开发作者,合作或者解答
  • ¥15 乳腺癌数据集 相关矩阵 特征选择
  • ¥15 我的游戏账号被盗取,请问我该怎么做
  • ¥15 通关usb3.0.push文件,导致usb频繁断连
  • ¥15 有没有能解决微信公众号,只能实时拍照,没有选择相册上传功能,我不懂任何技术,,有没有给我发个软件就能搞定的方法
  • ¥15 Pythontxt文本可视化
  • ¥15 如何基于Ryu环境下使用scapy包进行数据包构造
  • ¥15 springboot国际化