卡牌

題目分析

想一下前面題的特點，是不是都出現了“最大邊長”，“最小的數”這種字眼，那么這里出現了“最多能湊出多少套牌”，我們可以考慮用二分。接下來我們要看一下他是否符合二段性，二分的關鍵在于二段性。

第一階段二段性分析

對于mid套牌，如果我們可以湊出來，那么我們可以確定套數小于mid的牌一定也可以，但是此時我需要找的是最多，那么mid一定比小于mid的值更大，所以小于mid的值我就不用管了，也就是我可以確定我能夠舍棄掉mid左邊的值。我還想要確定比mid更大的值是否也滿足條件，所以我要在mid的右邊繼續二分。

if (check(mid)) {l = mid;} //因為mid是符合條件的，所以我要留著它，而不是l=mid+1

對于mid套牌，如果我們不可以湊出來，那么我們可以確定大于mid的套數一定也不可以，所以大于等于mid的值我就不用管了，也就是我可以確定我能夠舍棄掉mid右邊的值。我還想要尋找比mid更小的值是否能滿足條件，所以我要在mid的左邊繼續二分。

else { r = mid - 1; }//因為mid是不符合條件的，所以我不要留著它，而不是r=mid
//主要這里出現了減法，那么求mid那么應該是（l+r+1）/2

綜上該題滿足二段性，可以用二分，二分的板子就不說了，接下來說一下check函數如何寫。

第二階段寫check函數

check(u)要實現的作用是檢查我能否湊出u套牌，也就是n種牌每一種的張數至少是n。我現在有m張空牌可以用，但是也有一個限制對于第i種牌，我手寫的個數不能超過b[i]，具體請看代碼，

public static boolean check(int num) {//num為可以湊出來的卡牌組數long temp = m;//備份空白牌的數量for (int i = 0; i < a.length; i++) {//遍歷卡牌if (a[i] >= num) continue;//如果卡牌數現在不滿足至少為num張int add = num - a[i];//需要添加的撲克牌數量temp -= add;if (temp < 0) return false;//如果剩余的牌不夠if (add > b[i]) return false;//如果超過預計需要畫的牌個數}return true;}

第三階段二分范圍確定

l的值好確定，就是0，那么r呢？先來看一下a[i]的最大值是1e4，也就是每種牌我最多有4e5張，b[i]也是最多可以手寫4e5張，那么加起來就是8e5，因此r可以取8e5+5。后面的5是隨便加的數，一般要比你算出來的大一些就可以。

題目代碼

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {static int n;static long m;static int[] a, b;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String line = br.readLine();n = Integer.parseInt(line.split(" ")[0]);m = Long.parseLong(line.split(" ")[1]);//空白牌的數量a = new int[n];b = new int[n];int l = 0, r = 800005;String[] s = br.readLine().split(" ");for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(s[i]);}s = br.readLine().split(" ");for (int i = 0; i < n; i++) {b[i] = Integer.parseInt(s[i]);}while (l < r) {//獲取最大值int mid = (l + r + 1) / 2;if (check(mid)) {l = mid;} else {r = mid - 1;}}System.out.println(l);}public static boolean check(int num) {//num為可以湊出來的卡牌組數long temp = m;//備份空白牌的數量for (int i = 0; i < a.length; i++) {//遍歷卡牌if (a[i] >= num) continue;//如果卡牌數現在不滿足int add = num - a[i];//需要添加的撲克牌數量temp -= add;if (temp < 0) return false;//如果剩余的牌不夠if (add > b[i]) return false;//如果超過預計需要畫的牌個數}return true;}
}