一、青蛙过河——22年省赛（JAVA解法）
题目链接：
问题描述
小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。
河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃 后使石头高度下降到 0 是允许的)。
小青蛙一共需要去学校上 x 天课, 所以它需要往返 2x 次。当小青蛙具有 一个跳跃能力 y 时, 它能跳不超过 y 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。
输入格式
输入的第一行包含两个整数 n,x, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意 2x 才是实际过河的次数。
第二行包含 n−1 个非负整数 H1,H2,⋯,Hn−1, 其中 Hi>0 表示在河中与 小青蛙的家相距 i 的地方有一块高度为 Hi 的石头, Hi=0 表示这个位置没有石头。
输出格式
输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。
样例输入
5 1 1 0 1 0
样例输出
4
样例说明
由于只有两块高度为 1 的石头，所以往返只能各用一块。第 1 块石头和对岸的距离为 4，如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4的跳跃能力。
60%解法：
importjava.util.Scanner; publicclass青蛙过河 { publicstaticvoidmain(String[] args) { Scannersc=newScanner(System.in); intn=sc.nextInt(); intx=sc.nextInt(); int []arr=newint[n]; int []brr=newint[n]; int []crr=newint[n]; for (inti=1;i<n;i++){ arr[i]=sc.nextInt(); brr[i]=brr[i-1]+arr[i]; } for (inti=n-1;i>=1;i--){ crr[n-i]=crr[n-i-1]+arr[i]; } for (inti=1;i<n;i++){ if (brr[i]>=2*x&&crr[i]>=2*x){ System.out.print(i); return; } } } }
100%解法：
importjava.util.Scanner; // 1:无需package// 2: 类名必须Main, 不可修改publicclassMain { publicstaticvoidmain(String[] args) { Scannersc=newScanner(System.in); intn=sc.nextInt(); longx=sc.nextLong(); long []arr=newlong[n+1]; for (inti=1;i<n;i++){ arr[i]=sc.nextLong()+arr[i-1]; } arr[n]=arr[n-1]+9999999999L; intl=0; intsum=0; for (inti=1;i<=n;i++){ if (arr[i]-arr[l]>=2L*x){ sum=Math.max(sum,i-l); l+=1; } } System.out.println(sum); } }
二、分巧克力——蓝桥杯17年省赛（JAVA解法）
题目链接：
题目描述
儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第ii 块是 Hi×Wi 的方格组成的长方形。为了公平起见，
小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：
- 形状是正方形，边长是整数;
- 大小相同;
例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
编辑
输出描述
输出切出的正方形巧克力最大可能的边长。
输入输出样例
示例
输入
2 10 6 5 5 6
输出
2
运行限制
- 最大运行时间：2s
- 最大运行内存: 256M
题目代码：
importjava.util.*; publicclass分巧克力 { staticintn=0; staticintk=0; staticint [] wi=newint [100010]; staticint [] hi=newint [100010]; staticbooleancheck(intmid){ intres=0; for(inti=1;i<=n;i++){ res+=(wi[i]/mid)*(hi[i]/mid); } if(res<k){ returnfalse; } returntrue; } publicstaticvoidmain(String [] args) { Scannerscan=newScanner(System.in); n=scan.nextInt();//n个巧克力k=scan.nextInt();//k个朋友for(inti=1;i<=n;i++){ wi[i]=scan.nextInt(); hi[i]=scan.nextInt(); } intl=1; intr=10005; while(l<=r){ intmid=(l+r)/2; if(check(mid)){ //如果当前的mid满足可以分给k个小朋友 那么就说明mid的值还可以更大//所以答案再mid的右边l=mid+1; }else{ r=mid-1; } } System.out.println(l-1); } }
