首页 > 其他 > 详细

HDU 5122 K.Bro Sorting(2014北京区域赛现场赛K题 模拟)

时间:2014-11-30 23:00:31      阅读:371      评论:0      收藏:0      [点我收藏+]

这题定义了一种新的排序算法,就是把一串序列中的一个数,如果它右边的数比它小

则可以往右边移动,直到它右边的数字比它大为止。

易得,如果来模拟就是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 long
11 #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题 模拟)

原文:http://www.cnblogs.com/wushuaiyi/p/4133711.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!