首页 > 其他分享 >P8647 [蓝桥杯 2017 省 AB] 分巧克力

P8647 [蓝桥杯 2017 省 AB] 分巧克力

时间:2023-05-09 19:22:55浏览次数:64  
标签:AB return P8647 mid 蓝桥 int 2017

P8647 [蓝桥杯 2017 省 AB] 分巧克力

暴力做法(60分)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n,k,sum;
bool judge(int x)
{
    //倍数判断
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int x1=a[i]/x;
        int y1=b[i]/x;
        ans+=x1*y1;
    } 
    if(ans>=k)
    return true;
    return false;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        sum+=a[i]*b[i];
    }
    sum/=k;
    //printf("%d",sum); 
    for(int i=1;i<=sum/i+1;i++)
    {
        if(!judge(i))
        {
            printf("%d",i-1);
            break;
        }
    }
    return 0;
}

二分做法(100分)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n,k,sum;
bool judge(int x)
{
    //倍数判断
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int x1=a[i]/x;
        int y1=b[i]/x;
        ans+=x1*y1;
    } 
    if(ans>=k)
    return true;
    return false;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        sum+=a[i]*b[i];
    }
    sum/=k;
    int l=1,r=100000;
    while(r>l)
    {
        int mid=(l+r+1)/2;
        if(!judge(mid))
        r=mid-1;
        else
        l=mid;
    }
    printf("%d",l); 
    return 0;
}

从左往右找第一个不可以/可以的数字  <模板>

int l = 0, r = n - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }

从右往左找第一个不可以/可以的数字  <模板>

int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }

 

标签:AB,return,P8647,mid,蓝桥,int,2017
From: https://www.cnblogs.com/cornfield/p/17383248.html

相关文章

  • 第十四届蓝桥杯省赛C++ B组(个人经历 + 题解)
    参赛感受这是我第一次参加蓝桥杯的省赛,虽然没什么参赛经验,但是自己做了很多前几届蓝桥杯的题,不得不说,这一届蓝桥杯省赛的难度相较于之前而言还是比较大的。之前很流行蓝桥杯就是暴力杯的说法,但是随着参赛人数的增多,比赛认可度的提升,比赛题目的质量也明显越来越高了。这次省赛涉及......
  • [李景山php] 20170504深入理解PHP内核[读书笔记]--第一章准备工作和背景知识--2
    第一节:环境搭建编译安装的关键点:配置编译安装环境,build-essential环境。1.1准备编译环境针对于ubuntu16.04下面建设编译安装环境:apt-getinstallbuild-essential1.2编译cd~/php-src./buildconf./configure–help#查看可用参数./configure–disable-all#编......
  • [每天例题]蓝桥杯 C语言 谁拿了最多奖学金
    谁拿了最多奖学金题目   题目要求1.只要符合条件就可以得奖,每项奖学金的获奖人数没有限制,每名学生也可以同时获得多项奖学金。2.每行是一位学生的数据,从左向右依次是姓名,期末平均成绩,班级评议成绩,是否是学生干部,是否是西部省份学生,以及发表的论文数。姓名是由大小写......
  • P8655 [蓝桥杯 2017 国 B] 发现环 题解
    题目概述题目传送门在一棵树中新增一条边,使得这个图产生一个环,求在环上的点。思路:拓补排序对于这道题显然不能生搬硬套拓补排序的模板。这道题中的图是一个无向图,而拓补排序却是处理有向图的一种思想。不难想到可以将无向图转化为有向图,即将对于每条无向边变换为双向建边,就......
  • [每天例题]蓝桥杯 C语言 最小公倍数
    最小公倍数题目 思路分析方法一:建立两个for循环,第一个for循环求最小公倍数,第二个for循环进行1至n的排列方法二:/*最小公倍数n项可以计算前面的n-1项例如;1、2、3、4、5、6的最小公倍数=1、2、3、4、5的最小公倍数和6的最小公倍数我们定义一个贡献度:贡献度(ai)%贡献度(ai-1)==0......
  • WEB|[HITCON 2017]SSRFme
    源码110.244.80.206<?phpif(isset($_SERVER['HTTP_X_FORWARDED_FOR'])){$http_x_headers=explode(',',$_SERVER['HTTP_X_FORWARDED_FOR']);$_SERVER['REMOTE_ADDR']=$http_x_headers[0];}#获取......
  • [每天例题]蓝桥杯 C语言 天干地支
    天干地支题目 思路分析1.我们首先定义两个二维数组,将天干和地支分别录入,或者建立两个指针录入天干地支2.选取一个年份作为基准,在这里选择的是2020年庚子年3.此时输入的年份便被分为三个部分:小于2020年,2020年,大于2020年4.小于2020年部分减去2020后得到一个负数,我们需要将......
  • [蓝桥杯 2017 国 C] 合根植物 题解
    题目传送门一道并查集模板题。没什么好说的,先给个并查集模板,神犇可以直接跳过。查找根:intfind_root(intn){if(fa[n]==n)returnn;returnfa[n]=find_root(fa[n]);}合并:voidmerge(intx,inty){intsx=find_root(x),sy=find_root(y);......
  • [NOIP2017 普及组] 跳房子
    这是一道很复杂有趣的题目题目描述跳房子,也叫跳飞机,是一种世界性的儿童游戏,也是中国民间传统的体育游戏之一。跳房子的游戏规则如下:在地面上确定一个起点,然后在起点右侧画 n 个格子,这些格子都在同一条直线上。每个格子内有一个数字(整数),表示到达这个格子能得到的分数。玩家......
  • 蓝桥杯刷题笔记
    0杂//ASCII码数字-48A=65a=97//字符串分割//从下标0开始取n-1个字符str=str.substr(0,n-1)//二维vector的添加数据以及遍历vector<vector<int>>v;for(inti=0;i<2;i++){ vector<int>tmp; for(intj=0;j<2;j++) { tmp.push_back(j); } v.pu......