---

题目回顾

A. Furniture Store
每次测试时间限制：$2$ 秒
每次测试内存限制：$256$ 兆字节

一家家具制造销售公司的网站上有 $n$ 种不同型号的沙发，编号从 $1$ 到 $n$。每款沙发有唯一的价格；第 $i$ 款沙发的价格为 $a_i$。

每位访问网站的顾客有自己的预算 $m$（愿意为沙发支付的金额）。顾客浏览沙发列表时，会寻找第一个价格不超过 $m$ 的沙发并订购。如果没有这样的沙发，顾客将离开网站，不购买任何东西。

公司希望找出永远不会被订购的沙发型号。你的任务是：确定不存在任何预算 $m$ 能让顾客选中该型号沙发的那些型号。

输入格式
第一行包含一个整数 $t$ $(1 \leq t \leq 1000)$ — 测试用例的数量。
每个测试用例的第一行包含一个整数 $n$ $(1 \leq n \leq 100)$。
第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq 100)$。

输出格式
对于每个测试用例：
第一行输出一个整数 $k$ — 无法被订购的型号数量。
第二行按升序输出 $k$ 个整数 — 无法被订购的型号编号。

---

题解

关键观察

顾客的购买规则是：按照编号从小到大浏览，遇到第一个价格不超过预算 $m$ 的沙发就下单。

注意到，如果存在某个 $j < i$ 且 $a_j \leq a_i$，那么：

• 当某位顾客的预算 $m$ 足以购买第 $i$ 款沙发时（即 $m \geq a_i$），必然也有 $m \geq a_j$；
• 由于 $j$ 排在 $i$ 前面，顾客会优先选择第 $j$ 款沙发，从而第 $i$ 款永远不会被购买。

反之，若 $a_i$ 严格小于它之前的所有价格：

$$a_i < \min\{a_1, a_2, \dots, a_{i-1}\}$$

则当顾客的预算 $m$ 满足：

$$a_i \leq m < \min\{a_1, a_2, \dots, a_{i-1}\}$$

时，前面所有沙发都超出了预算，唯有第 $i$ 款沙发可以被购买。因此，该款沙发是会被购买的。

---

充分必要条件

综上，我们得到核心结论：

$$\boxed{ \text{第 } i \text{ 款沙发会被订购} \iff a_i = \min\{a_1, a_2, \dots, a_i\} } $$

换句话说，永远不会被订购的沙发就是那些在其前缀中不是最小值的型号。

---

解法

我们只需遍历一次数组 $a$，维护当前前缀的最小值 min_so_far：

• 初始令 $\text{min\_so\_far} = +\infty$
• 对于每个 $i$ 从 $1$ 到 $n$：
  • 若 $a_i < \text{min\_so\_far}$：说明 $a_i$ 是其前缀的最小值，会被订购，并更新 $\text{min\_so\_far} = a_i$；
  • 否则：$a_i$ 不是前缀最小值，不会被订购，将 $i$ 加入答案列表。

由于按 $i$ 从小到大遍历，加入答案列表的索引自然满足升序要求。

---

最终算法

1. 初始化答案列表 ans 为空。
2. 初始化 min_so_far = ∞。
3. 对于 $i = 1, 2, \dots, n$：
   • 如果 $a_i < \text{min\_so\_far}$：
     • $\text{min\_so\_far} \gets a_i$
   • 否则：
     • 将 $i$ 加入 ans
4. 输出 ans 的大小和内容。

---

复杂度分析

每个测试用例只需 $O(n)$ 时间遍历一次数组，$n \leq 100$，总用例数 $t \leq 1000$，完全可行。空间复杂度 $O(n)$ 用于存储输入数组和答案。

---

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector<int> ans;
    int min_so_far = INT_MAX;
    
    for (int i = 0; i < n; i++) {
        if (a[i] < min_so_far) {
            min_so_far = a[i];  // 是前缀最小值，会被购买
        } else {
            ans.push_back(i + 1);  // 不是前缀最小值，不会被购买
        }
    }
    
    cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " \n"[i == ans.size() - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

示例验证

输入：

4
3
1 2 3
4
4 6 2 1
1
100
6
7 5 8 4 6 2

处理过程：

• 用例 1：$a=[1, 2, 3]$
  前缀最小值变化：$1 \to 1 \to 1$
  $a_1=1$ 是最小值（卖）；$a_2=2$ 不是（不卖）；$a_3=3$ 不是（不卖）
  → 答案：$[2, 3]$，数量 $k=2$ ✅

• 用例 2：$a=[4, 6, 2, 1]$
  前缀最小值变化：$4 \to 4 \to 2 \to 1$
  $a_1=4$ 卖；$a_2=6$ 不卖；$a_3=2$ 卖（新最小值）；$a_4=1$ 卖（新最小值）
  → 答案：$[2]$，数量 $k=1$ ✅

• 用例 3：$a=[100]$
  前缀最小值：$100$
  $a_1=100$ 卖
  → 答案为空，数量 $k=0$ ✅

• 用例 4：$a=[7, 5, 8, 4, 6, 2]$
  前缀最小值变化：$7 \to 5 \to 5 \to 4 \to 4 \to 2$
  $a_1=7$ 卖；$a_2=5$ 卖；$a_3=8$ 不卖；$a_4=4$ 卖；$a_5=6$ 不卖；$a_6=2$ 卖
  → 答案：$[3, 5]$，数量 $k=2$ ✅

输出：

2
2 3
1
2
0

2
3 5

与题目示例完全一致。