蓝桥杯 2017年第八届真题 分巧克力 经典的二分答案 输入挂
问题 1885: [蓝桥杯][2017年第八届真题]分巧克力
时间限制: 1Sec 内存限制: 128MB 提交: 360 解决: 80
题目描述
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
1. 形状是正方形，边长是整数
2. 大小相同
例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？
输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。
输出
输出切出的正方形巧克力最大可能的边长。
样例输入
2 10
6 5
5 6样例输出
2先贴个输入挂的模板，官网没给好java用例，只能手动提速了，或者你改成c++代码趴qaq
//解决javaIO读取过慢的方法，利用该类读取输入数据，不要用Scanner！！！
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
public static void main(String[] args) {
InputReader in = new InputReader(System.in); //用它来代替Scanner。
二分答案的模板结构如下：
边界跳出和输出很重要，可以用l=1,r=2来给自己举列子，如果1是答案，2是答案这样脑补下
while(l<=r) {
int mid = l + (r-l)/2;
if(ok(mid)) {
l=mid+1;
}else
r = mid - 1;
}
System.out.println(r);ok()函数需要自己写，什么时候用二分答案呢，一般是题目说尽可能大，又什么要最大又要最小之类的
static boolean ok(int x) {
int ans=0,u=0,v=0;
for(int i=0;i<n;i++) {
u=H[i]/x;
v=W[i]/x;
ans+=u*v;
if(ans>=k)
return true;
}
return false;
}AC代码，蓝桥杯官网过不了没写输入挂的java代码，c语言oj可以，或者你改成c++代码
一个5x6的巧克力能分多少个2x2的巧克力呢，(5/2)x(6/2)=6,发现规律了吧，对边长分配除大小,如果巧克力是2x3不是正方形呢，那这样的话，可能就是大边除大边，小边除小边了(瞎猜)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 分巧克力 {
//解决javaIO读取过慢的方法，利用该类读取输入数据，不要用Scanner！！！
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
public static void main(String[] args) {
InputReader in = new InputReader(System.in); //用它来代替Scanner。
n = in.nextInt();
k = in.nextInt();
H = new int[n+5];
W = new int[n+5];
int l=1,r=100000;
for(int i=0;i<n;i++) {
H[i] = in.nextInt();
W[i] = in.nextInt();
}
while(l<=r) {
int mid = l + (r-l)/2;
if(ok(mid)) {
l=mid+1;
}else
r = mid - 1;
}
System.out.println(r);
}
static int n,k;
static int[] H;
static int[] W;
static boolean ok(int x) {
int ans=0,u=0,v=0;
for(int i=0;i<n;i++) {
u=H[i]/x;
v=W[i]/x;
ans+=u*v;
if(ans>=k)
return true;
}
return false;
}
}
近期遇到过的牛客比赛——二分答案
华华给月月准备礼物
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？
输入描述:
第一行两个正整数N、K，表示木棍原本的根数和华华希望得到的木棍根数。
第二行N个正整数LiLi表示每根木棍的初始长度。输出描述:
输出一行一个非负整数表示每根木棍的最大长度。示例1
输入
5 10
4 4 4 5 3输出
1说明
如果长度为2，只能得到2+2+2+2+1=9根，不够；长度为1可以得到4+4+4+5+3=20根，足够。所以答案最大是1。示例2
输入
5 3
1 2 3 4 5输出
3备注:
1≤N≤2×10^5,1≤N≤2×10^5,1≤Li≤10^9,1≤Li≤10^9，1≤K≤10^9
这题你很自然的可以从1慢慢枚举到答案，但这时你也应该可以想到找出答案的边界,二分的枚举出边界
import java.util.Scanner;
public class 华华给月月准备礼物 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
k = in.nextInt();
a = new int[n];
for(int i=0;i<n;i++) {
a[i] = in.nextInt();
r = Math.max(r, a[i]);
}
while(l<=r) {
int mid = l + (r-l)/2;
if(ok(mid)) {
l = mid+1;
}
else
r = mid-1;
}
System.out.println(r);
}
static int[] a;
static int n,k,l=1,r=0;
static boolean ok(int x) {
int ans = 0;
for(int i=0;i<n;i++)
ans += a[i]/x;
return ans>=k;
}
}