求解Google Code Jam 2018 Round 1C Q3：LIS解法未通过小测试集存疑

嘿，我来帮你分析下这个问题～

你提到的Google Code Jam 2018 Round 1C第三题（Ant Stack）的核心约束是：将一只蚂蚁加入已有蚁堆时，蚁堆当前的总重量必须≤该蚂蚁重量的6倍。而最长递增子序列（LIS）的核心逻辑是基于元素间的大小递增关系，这和题目中的总重量约束并不等价——即使蚂蚁重量递增，堆的总重量也可能超过新蚂蚁重量的6倍，导致无法加入堆中。

举个简单的反例：假设有8只重量均为7的蚂蚁。LIS的长度是8（所有元素非递减），但实际上，当你尝试把第7只7加入堆时，堆的总重量是67=42，刚好满足42≤67；但第8只7加入时，堆的总重量是77=49>67=42，无法加入。因此最长合法堆的长度是7，而LIS给出的结果是8，这就导致了错误。

如果题目要求的是单个蚁堆能容纳的最多蚂蚁数量，正确的思路是结合贪心+二分查找，维护一个dp数组：

• 将所有蚂蚁按重量从小到大排序（小蚂蚁放在堆底，总重量增长更慢，能容纳更多后续蚂蚁）
• dp[k]表示长度为k的蚁堆的最小总重量。这样我们可以用最小的总重量来构建长度为k的堆，为后续蚂蚁留出更多空间。
• 对于每只蚂蚁w，用二分查找找到最大的k，使得dp[k] ≤ 6*w。如果找到，就更新dp[k+1] = dp[k] + w；如果没找到（即k=0），则新建一个长度为1的堆，dp[1] = w。
• 最终dp数组的最大长度就是答案。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            int N = Integer.parseInt(br.readLine());
            long[] weights = new long[N];
            String[] parts = br.readLine().split(" ");
            for (int i = 0; i < N; i++) {
                weights[i] = Long.parseLong(parts[i]);
            }
            Arrays.sort(weights);
            
            // dp数组，dp[i]表示长度为i的堆的最小总重量
            long[] dp = new long[N+1];
            dp[0] = 0; // 长度为0的堆总重量0
            int maxLen = 0;
            
            for (long w : weights) {
                // 找最大的k，使得dp[k] <= 6*w
                int left = 0, right = maxLen;
                int best = 0;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (dp[mid] <= 6 * w) {
                        best = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                // 可以构建长度为best+1的堆
                if (best + 1 > maxLen) {
                    maxLen = best + 1;
                }
                if (dp[best+1] == 0 || dp[best] + w < dp[best+1]) {
                    dp[best+1] = dp[best] + w;
                }
            }
            System.out.printf("Case #%d: %d%n", t, maxLen);
        }
    }
}

如果题目要求的是将所有蚂蚁分成满足条件的蚁堆，求最少的堆数，思路会稍有不同：

1. 同样先按重量从小到大排序
2. 维护一个列表存储每个堆的总重量，保持列表有序
3. 对于每只蚂蚁w，用二分查找找到最大的总重量S，使得S <=6*w。如果找到，就将该堆的总重量更新为S+w；如果没找到，就新建一个堆（添加w到列表）
4. 最终列表的大小就是最少堆数

对应的Java代码可以调整为：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            int N = Integer.parseInt(br.readLine());
            long[] weights = new long[N];
            String[] parts = br.readLine().split(" ");
            for (int i = 0; i < N; i++) {
                weights[i] = Long.parseLong(parts[i]);
            }
            Arrays.sort(weights);
            
            ArrayList<Long> piles = new ArrayList<>();
            for (long w : weights) {
                long limit = 6 * w;
                // 找最大的pile总重量<=limit
                int idx = Collections.binarySearch(piles, limit);
                if (idx < 0) {
                    idx = -idx -2; // 转换为最大的<=limit的索引
                }
                if (idx >=0) {
                    // 更新该pile的总重量
                    piles.set(idx, piles.get(idx) + w);
                    // 重新排序piles，保持有序
                    Collections.sort(piles);
                } else {
                    // 新建pile
                    piles.add(w);
                }
            }
            System.out.printf("Case #%d: %d%n", t, piles.size());
        }
    }
}

你可以根据题目实际要求选择对应的解法，应该能通过小测试集了～

内容的提问来源于stack exchange，提问作者jas7