首页 > 代码库 > 1011 K.Bro Sorting
1011 K.Bro Sorting
·2号题
·举个例子来进行说明: 5 2 3 1 7 4 6
思路:
维护一个最小值t,初始为最后一个数,这里为6;
我们从后向前考虑,先看末尾6,其前面为4,不需要动,更改t为更小的4;
再向前,为7,此时7>t,那么对于7来说,其肯定是需要动的,令num++;
再向前,1<t,令t=1;
再向前,因为t为1,所有值都会>t,对于3、2、5来说,都需要进行num++。
这里num加了4次,结果为4.
解释:
因为题目中交换数字有一个特点,就是选择一个数字x,从前向后进行,一直进行到x<其后面的数字;
那么对于每一个数字来说,只要其后面存在比它小的数字,其都要进行一次移位!
(这句话的意思就是从当前数字之后的所有数字中找到最小值,与其比较;我们从后向前进行,可以对最小值进行维护,大大降低时间复杂度),
AC Code:
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #include <cstring> 5 #include <string.h> 6 #include <math.h> 7 #include <queue> 8 #include <stack> 9 #include <stdlib.h>10 #include <map>11 using namespace std;12 13 #define LL long long 14 #define sf(a) scanf("%d",&(a));15 #define inf 2e916 #define INF 214748364717 #define N 2518 #define PI 3.14159265319 #define EPS 1e-820 21 int f[N];22 int main(){23 int T,n;int k=1;24 scanf("%d",&T);25 while(T--){26 scanf("%d",&n);27 for(int i=0;i<n;i++){28 scanf("%d",&f[i]);29 }30 int num=0;int t = f[n-1];31 for(int i=n-2;i>=0;i--)32 if(f[i]>t) num++;33 else t = f[i];34 printf("Case #%d: ",k++);35 printf("%d\n",num);36 }37 return 0;38 }
1011 K.Bro Sorting
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。