Wikipedia

(

( 1

( 1 4

( 1 4 2

Second Round:

(

( 1

( 1 2

( 1 2 4

The input may contain several cases.

The first line contains an integer*T* (*T* ≤ 100,000), indicating the number of test cases.

Then*T* lines of test cases follow. For each line, it contains two integers *N* and *K* (1 ≤ *N* ≤ 1,000,000, 0 ≤ *K* ≤ *N* - 1) where *N* is the size of array and *K* is the number of Bubble Sort Rounds.

The first line contains an integer

Then

Suppose the ordered array is {a, b, c} (a < b < c). For the 6 possible initial arrays:

{a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a},

we can get that:

{a, b, c}: already sorted, no bubble sort needed.

{a, c, b}, {b, a, c}, {c, a, b}: we need 1 round of Bubble Sort.

{b, c, a}, {c, b, a}: we need 2 rounds of Bubble Sort.

提交代码