首页 > 代码库 > HDU 5122 K.Bro Sorting（2014北京区域赛现场赛K题 模拟）
HDU 5122 K.Bro Sorting（2014北京区域赛现场赛K题 模拟）
这题定义了一种新的排序算法，就是把一串序列中的一个数，如果它右边的数比它小
则可以往右边移动，直到它右边的数字比它大为止。
易得，如果来模拟就是O(n^2)的效率，肯定不行
想了一想，这个问题可以被转化成
求这一串序列当中每个元素，它的右边是否存在小于它的数字，如果存在，则++ans
一开始没想到诶= = 不应该不应该
1 //#pragma comment(linker, "/STACK:16777216") //for c++ Compiler 2 #include <stdio.h> 3 #include <iostream> 4 #include <cstring> 5 #include <cmath> 6 #include <stack> 7 #include <queue> 8 #include <vector> 9 #include <algorithm>10 #define ll long long11 #define Max(a,b) (((a) > (b)) ? (a) : (b))12 #define Min(a,b) (((a) < (b)) ? (a) : (b))13 #define Abs(x) (((x) > 0) ? (x) : (-(x)))14 15 using namespace std;16 17 const int INF = 0x3f3f3f3f;18 int a[1000001];19 20 int main(){21 int i, j, k, t, n, m, numCase = 0;22 scanf("%d",&t);23 while(t--){24 scanf("%d",&n);25 for(i = 0; i < n; ++i) scanf("%d",&a[i]);26 int ans = 0;27 for(i = n - 2; i >= 0; --i){28 if(a[i] > a[i + 1]){29 swap(a[i], a[i + 1]);30 ++ans;31 }32 }33 printf("Case #%d: %d\n",++numCase, ans);34 }35 return 0;36 }
HDU 5122 K.Bro Sorting（2014北京区域赛现场赛K题 模拟）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。