神州信息笔试 - 1009

小乐的数字

题面

小乐乐喜欢数字，尤其喜欢 $0$ 和 $1$。他现在得到了一个数，想把每位的数变成 $0$ 或 $1$。如果某一位是奇数，就把它变成 $1$，如果是偶数，那么就把它变成 $0$。请你回答他最后得到的数是多少。

输入描述:
输入包含一个整数 $n (0 ≤ n ≤ 10^9)$

输出描述:
输出一个整数，表示小乐乐改后得到的数字。

示例：

输入：222222
输出：0

思路与代码：

将一个整数的每一位数字进行转换，如果某一位是奇数，则将其变为 $1$，如果是偶数，则将其变为 $0$。最终将这些转换后的数字重新组合成一个新的整数。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        String str = String.valueOf(n);
        StringBuilder res = new StringBuilder();
        
        for (char c : str.toCharArray()) {
            int x = c - '0';
            if (x % 2 == 0) {
                res.append('0');
            } else {
                res.append('1');
            }
        }
        
        System.out.println(Integer.parseInt(res.toString()));
    }
}

餐馆

题面

某餐馆有 $n$ 张桌子，每张桌子可以最多容纳 $a_i$ 个人。有 $m$ 批客人，每批客人人数为 $b_i$, 预计消费金额为 $c_i$。在不允许拼桌的情况下，请问该预订消费金额最大是多少？

输入描述:
第一行两个整数 $n, m(1 \leq n \leq 50000, 1 \leq m \leq 50000)$，分别代表桌子数和客人的批次。
第二行为 $n$ 个整数 $a_i$，即每个桌子可容纳的最大人数，以空格分隔。
接下来 $m$ 行，每行两个整数 $b_i,c_i$，分别表示第 $i$ 批客人的人数和预计消费金额以空格分隔，范围均在 $32$ 位 int 范围内。

输出描述:
输出一个整数，表示最大的总预计消费金额。

思路与代码：

先对所有桌子按容纳人数从小到大排序，再对所有客人按消费金额从大到小排序。优先安排消费金额高的客人。

对于每批客人，找到能容纳他们的最小桌子，这样就可以最大程度地利用桌子资源。即最小值最大问题，典型的二分。

如果可以分配，则记录该批客人的消费金额，并标记该桌子已被占用。最后累加所有成功分配的客人的消费金额，即为最大总预计消费金额。

理论上来说，这个思路是没有问题的，实际上超时了，只过了 $60\%$。
不理解，怀疑是数据有问题。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int[] table= new int[n];
        for (int i = 0; i < n; i++) {
            table[i] = sc.nextInt();
        }
        
        int[][] guests = new int[m][2];
        for (int i = 0; i < m; i++) {
            guests[i][0] = sc.nextInt();
            guests[i][1] = sc.nextInt();
        }
        
        Arrays.sort(table);
        Arrays.sort(guests, (a, b) -> b[1] - a[1]);
        
        boolean[] tableUsed = new boolean[n];
        long maxTotalMoney = 0;
        
        for (int i = 0; i < m; i++) {
            int numGuests = guests[i][0];
            int money = guests[i][1];
            int index = binarySearch(tableCapacity, numGuests);
            
            if (index != -1 && !tableUsed[index]) {
                maxTotalMoney += money;
                tableUsed[index] = true;
            }
        }
        
        System.out.println(maxTotalMoney);
    }
    
    private static int binarySearch(int[] table, int numGuests) {
        int l = 0, r = table.length - 1;
        int res = -1;
        
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (table[mid] >= numGuests) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        return res;
    }
}