{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"去年的平安夜,因为还没有进入算法组所以孤单的tzx同学在宿舍学习了冒泡排序。\n```cpp\nvoid bubbleSort (int arr[], int len) {\n int temp;\n int i, j;\n for (i\u003d0; i\u003clen-1; i++) \n for (j\u003d0; j\u003clen-1-i; j++) { \n if (arr[j] \u003e arr[j+1]) { \n temp \u003d arr[j];\n arr[j] \u003d arr[j+1];\n arr[j+1] \u003d temp;\n }\n }\n}\n```\n过于无聊的他想到一个问题:给一个序列,我们使用冒泡排序法对它进行排序,在排序过程中会进行多少次交换?\n于是他对上面的代码进行了改造\n```cpp\nint bubbleSort (int arr[], int len) {\n int temp;\n int i, j;\n int cnt\u003d0;\n for (i\u003d0; i\u003clen-1; i++) \n for (j\u003d0; j\u003clen-1-i; j++) { \n if (arr[j] \u003e arr[j+1]) { \n temp \u003d arr[j];\n arr[j] \u003d arr[j+1];\n arr[j+1] \u003d temp;\n cnt++;\n }\n }\n return cnt;\n}\n```\n可是这样这样做对于较大的数据量是无法在1s之内得出结果的(会超时),tzx同学很是苦恼。\n还好,在水秀老师的带领下,他很快的学习到了如何解决这个问题。\n(注:后来才发现,这题是水秀老师每周要求中的一道必做题~)\n![img](CDN_BASE_URL/b3530eaa8fa98ef394d3639722240a8c?v\u003d1602813316)\n\n"}},{"title":"Input","value":{"format":"MD","content":"输入包含多个测试用例\n\n每个测试用例第一行为一个整数n(n\u003c500000)表示数组的长度 \n下面n行每一行包含一个整数0≤a[i]≤999,999,999,即数组中第i个元素的值。 \n\n当n\u003d0时结束输入"}},{"title":"Output","value":{"format":"MD","content":"对于每个输入序列,程序打印一个数op,即对给定输入序列进行排序所需的最小交换操作数。\n(注:交换操作数可能很大)"}},{"title":"Sample Input","value":{"format":"MD","content":"\u003cpre class\u003d\"sio\"\u003e5\n9\n1\n0\n5\n4\n3\n1\n2\n3\n0\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"MD","content":"\u003cpre class\u003d\"sio\"\u003e6\n0\n\u003c/pre\u003e"}}]}