排队取号
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Problem Description
事实上,silverwolf 发现需要排队最少的那家餐厅也需要排两个小时队,天塌了。
silverwolf 和学弟学妹们一起去觅食。周末的餐厅人满为患,她在 $n$ 家餐厅完成了取号,第 $i$ 家餐厅前面还有 $a_i$ 人在排队。
silverwolf 决定从第 $1$ 家餐厅的号码开始依次往下看。在看的过程中以此进行以下行为:
$\quad$· 如果当前是看到的第一个号码,或当前号码严格小于之前看到的所有号码,她会把之前攒着的所有号码全部扔进垃圾桶,只留下当前这一张。
$\quad$· 将当前号码追加到手中。
扫描完所有 $n$ 家餐厅后,silverwolf 手中会握有一些号码。她会选择手中的第一张号码所对应的餐厅去吃饭。
请输出这家餐厅的编号。
Input Format
第一行一个整数 $T$($1 \le T \le 1000$),表示测试数据组数。
每组数据:
第一行一个整数 $n$($1 \le n \le 2 \times 10^5$),表示餐厅数量。
第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$($1 \le a_i \le 10^9$),表示每家餐厅前方排队的人数。
保证所有测试数据的 $\sum n \le 2 \times 10^5$。
Output Format
对于每组数据,输出一行一个整数,表示 silverwolf 最终选择的餐厅编号。
2
3
3 1 2
5
4 4 3 1 4
2
4
1
4
1 2 3 4
1
Hint
对于第一组样例的第一组数据 $[3, 1, 2]$:
$\quad$· 看 $3$:第一个,保留 $[3]$;
$\quad$· 看 $1$:$1 < 3$,丢掉 $3$,保留 $[1]$;
$\quad$· 看 $2$:$2 < 1$ 不成立,追加,手上变为 $[1, 2]$。
手中第一张 $1$ 来自第 $2$ 家餐厅,输出 $2$。
对于第一组样例的第二组数据 $[4, 4, 3, 1, 4]$:
$\quad$· 看 $4$:保留 $[4]$;
$\quad$· 看 $4$:追加,$[4, 4]$;
$\quad$· 看 $3$:$3 < 4$,丢掉,保留 $[3]$;
$\quad$· 看 $1$:$1 < 3$,丢掉,保留 $[1]$;
$\quad$· 看 $4$:追加,$[1, 4]$。
手中第一张 $1$ 来自第 $4$ 家餐厅,输出 $4$。
2026江南程序设计竞赛联盟暑期多校训练-第一场(重现)
- Status
- Done
- Rule
- XCPC
- Problem
- 12
- Start at
- 2026-10-17 12:00
- End at
- 2026-10-17 17:00
- Duration
- 5 hour(s)
- Host
- Partic.
- 0