思路

这个问题的核心是找到一个零食的子集（Tk的零食），其总价格 $S_{Tk}$ 在满足 $S_{Tk} \leq S_{弟弟}$ 的前提下，使得差值 $S_{弟弟} - S_{Tk}$ 最小。

设所有零食的总价格为 $S_{总} = \sum_{i=1}^{n} a_i$。 因为所有零食必须被分配，所以有 $S_{Tk} + S_{弟弟} = S_{总}$。 将此式代入条件1，得到 $S_{Tk} \leq S_{总} - S_{Tk}$，化简后为 $2S_{Tk} \leq S_{总}$，即 $S_{Tk} \leq S_{总} / 2$。

同时，我们要最小化 $S_{弟弟}$ - $S_{Tk}$ = ($S_{总}$ - $S_{Tk}$) - $S_{Tk}$ = $S_{总}$ - $2S_{Tk}$。 要最小化这个差值，就需要最大化 $S_{Tk}$。

所以，问题转化为了：从所有零食中为Tk选择一个子集，使得其总价格 $S_{Tk}$ 最大，但不能超过所有零食总价格的一半（$S_{总} / 2$）。

这是一个典型的子集和问题（背包问题变体）。通常情况下，这是NP-难题，但本题中零食的价格是 $m$ 的幂次方（$m^1, m^2, \ldots, m^n$），具有特殊性质，使得问题可以用贪心策略解决。我们需要分两种情况讨论。

情况一：$m = 1$

当 $m=1$ 时，所有零食的价格都是 $1^i = 1$。 总共有 $n$ 件零食，总价格 $S_{总} = n$。 Tk需要满足 $S_{Tk} \leq n / 2$。由于每个零食价格为 $1$，$S_{Tk}$ 就等于Tk拿到的零食数量 $k$。 所以条件为 $k \leq n / 2$。为了最大化 $S_{Tk}$（即最大化 $k$），Tk应该拿 $\lfloor n/2 \rfloor$ 件零食。 由于所有零食价格相同，拿哪些零食对总价没有影响。我们可以简单地让他拿编号为 $1, 2, \ldots, \lfloor n/2 \rfloor$ 的零食。

情况二：$m \ge 2$

当 $m \ge 2$ 时，价格序列 $m^1, m^2, \ldots, m^n$ 是一个快速增长的几何级数。它有一个非常重要的性质： $a_k$ = $m^k$ $>$ $\sum_{i=1}^{k-1} m^i$ = $\sum_{i=1}^{k-1} a_i$ 这个性质对于所有 $k > 1$ 成立。这意味着，任何一个零食的价格都比所有比它便宜的零食的价格总和还要大。

利用这个性质，我们可以找到最优的分配方案。考虑价格最高的零食 $a_n=m^n$。 总价格 $S_{总}$ = $\sum_{i=1}^{n} m^i$ = $a_n$ + $\sum_{i=1}^{n-1} a_i$。 由于 $a_n$ $>$ $\sum_{i=1}^{n-1} a_i$，我们知道 $a_n$ 超过了总价的一半。 如果Tk拿了第 $n$ 件零食，他的总价 $S_{Tk}$ 至少为 $a_n$。而弟弟最多只能拿到剩下的零食，总价为 $\sum_{i=1}^{n-1} a_i$。这将导致 $S_{Tk} > S_{弟弟}$，违反了条件。 所以，Tk绝对不能拿第 $n$ 件零食。第 $n$ 件零食必须给弟弟。

现在，弟弟已经拿了第 $n$ 件零食（价格 $a_n$），Tk一件还没拿。剩下的零食是 $\{1, 2, \ldots, n-1\}$。 当前的价格状况是 $S_{Tk} = 0$，$S_{弟弟} = a_n$。 为了让两人的价格差最小，Tk应该尽可能多地从剩下的零食中拿取，以追赶弟弟的价格。 Tk能把剩下的所有零食（$\{1, 2, \ldots, n-1\}$）都拿走吗？ 如果Tk拿走所有剩下的零食，那么他的总价是 $S_{Tk} = \sum_{i=1}^{n-1} a_i$。弟弟的总价是 $S_{弟弟} = a_n$。 根据我们之前提到的性质，$a_n > \sum_{i=1}^{n-1} a_i$，所以此时仍然满足 $S_{Tk} < S_{弟弟}$。 这使得两人的价格差为 $a_n - \sum_{i=1}^{n-1} a_i$。如果我们从Tk的集合中拿走任何一件零食给弟弟，他们之间的价格差都会变得更大。因此，这是能达到的最小价格差。

所以，当 $m \ge 2$ 时，最优解是：

• 弟弟拿第 $n$ 件零食。
• Tk拿剩下的所有零食，即 $\{1, 2, \ldots, n-1\}$。
• 如果 $n=1$，Tk什么也拿不到，因为唯一的一件必须给弟弟。这个情况也符合 $n-1=0$ 的结论。

C++

#include <iostream>
#include <vector>
#include <numeric>

void solve() {
    long long n;
    long long m;
    std::cin >> n >> m;

    if (m == 1) {
        // 如果m=1，所有零食价格都为1
        // Tk拿n/2（向下取整）个零食，使其总价最大且不超过总价的一半
        long long k = n / 2;
        std::cout << k << std::endl;
        for (long long i = 1; i <= k; ++i) {
            std::cout << i << (i == k ? "" : " ");
        }
        std::cout << std::endl;
    } else {
        // 如果m>=2，价格为m的幂
        // 价格最高的零食m^n比其他所有零食的总和还要贵
        // 为了满足 S_tk <= S_bro, 价格最高的零食n必须给弟弟
        // 为了最小化差值，剩下的 n-1 个零食都给Tk
        long long k = n - 1;
        if (k < 0) k = 0; // 处理 n=0 的边缘情况
        std::cout << k << std::endl;
        for (long long i = 1; i <= k; ++i) {
            std::cout << i << (i == k ? "" : " ");
        }
        std::cout << std::endl;
    }
}

int main() {
    // 提高C++ IO效率
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Python

import sys

def solve():
    """
    处理单组测试数据的函数。
    """
    try:
        # 从一行中读取 n 和 m
        n, m = map(int, sys.stdin.readline().split())
    except (IOError, ValueError):
        # 如果读取失败（例如文件末尾），则返回
        return

    # 根据 m 的值决定分配策略
    if m == 1:
        # 如果 m=1，所有零食价格都为1。
        # Tk拿 n // 2（向下取整）个零食，使其总价最大且不超过总价的一半。
        k = n // 2
    else: # m >= 2
        # 如果 m>=2，价格为m的幂。
        # 价格最高的零食 m^n 比其他所有零食的总和还要贵。
        # 为了满足 S_tk <= S_bro，价格最高的零食 n 必须给弟弟。
        # 为了最小化差值，剩下的 n-1 个零食都给Tk。
        k = n - 1
        # 题目约束 n>=1，所以 k>=0，无需像C++代码中那样检查 k < 0。

    # 输出Tk拿到的零食数量
    print(k)

    # 输出Tk拿到的零食编号
    if k > 0:
        # 生成从1到k的编号列表
        items = list(range(1, k + 1))
        # 使用 * 操作符解包列表，打印出 "1 2 3..." 的格式
        print(*items)
    else:
        # 如果k=0，Tk不拿任何零食，第二行为空。
        # print()会输出一个换行符，产生一个空行，与C++代码行为一致。
        print()


def main():
    """
    主函数，处理所有测试数据。
    """
    try:
        # 读取测试数据组数 T
        num_tests_str = sys.stdin.readline()
        if not num_tests_str:
            return
        num_tests = int(num_tests_str)
        
        # 循环T次执行解题函数
        for _ in range(num_tests):
            solve()
            
    except (IOError, ValueError):
        return

# 程序入口
if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

    // solve方法处理单个测试用例
    public static void solve(FastReader sc, PrintWriter out) {
        long n = sc.nextLong();
        long m = sc.nextLong();

        long k;
        if (m == 1) {
            // 如果m=1，所有零食价格都为1。
            // Tk拿n/2（向下取整）个零食，使其总价最大且不超过总价的一半。
            k = n / 2;
        } else {
            // 如果m>=2，价格为m的幂。
            // 价格最高的零食m^n比其他所有零食的总和还要贵。
            // 为了满足 S_tk <= S_bro, 价格最高的零食n必须给弟弟。
            // 为了最小化差值，剩下的 n-1 个零食都给Tk。
            k = n - 1;
            // 题目约束 n>=1，所以 k>=0，无需像C++代码中那样检查 k < 0。
        }

        // 输出Tk拿到的零食数量
        out.println(k);

        // 输出Tk拿到的零食编号
        if (k > 0) {
            for (long i = 1; i <= k; ++i) {
                // 使用三元运算符来处理空格，最后一个数字后不加空格
                out.print(i + (i == k ? "" : " "));
            }
            // 打印完所有编号后换行
            out.println();
        } else {
            // 如果k=0，第二行为空行，与C++代码行为一致
            out.println();
        }
    }

    // 主函数
    public static void main(String[] args) {
        // 使用自定义的FastReader和PrintWriter以提高IO效率
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(System.out);

        // 读取测试用例的数量
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc, out);
        }

        // 关闭writer，确保所有缓冲区的输出都被写入
        out.flush();
        out.close();
    }

    // 用于快速IO的辅助类
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

题目内容

$Tk$ 和他的弟弟买了$n$种不同的零食(编号从1开始)，每种零食各一个。给定整数$m$以及价格表{$a_1,a_2，..,a_n$},其中a1=m且对任意$2≦i≦n$有$a_i=a_{i-1}×m$。编号为i的零食价格为$ai$。

现在需要把全部零食在两人之间分配(每件零食必须属于其中一人)。$Tk$作为哥哥，希望自己拿到的零食总价格不超过弟弟零食的总价格;在满足上述条件下，$Tk$为了照顾弟弟的自尊心希望两人的总价格差尽可能小。请输出Tk最终拿到的零食编号(编号顺序任意)。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤10^4)$代表数据组数，每组测试数据描述如下:

在一行上输入两个整数，使用变量$n、m (1≦n≦2×10^5;1≦m≦10^9)$指代,分别表示零食种类数与 价格倍率。

除此之外，保证单个测试文件的n之和不超过$2×10^5$

输出描述

对于每一组测试数据，新起一行输出:

• 第一行输出一个整数$k$,表示$Tk$拿到的零食个数;
• 第二行输出$k$个整数，要求两两不同，表示$Tk$拿到的零食编号(顺序任意)。

当$k=0$时,第二行留空。

样例1

输入

2
1 2 
5 1

输出

0

2
1 2

说明

当$n=1,m=2$时,价格为{$2$}，若$Tk$拿走它将违反不超过条件,因此$k=0$；

当$n=5,m=1$时,价格全为$1$，选取编号$1,2$得到$2$的价格,弟弟得到剩余$3$的价格，可以证明不存在更优的方案。