题意：把冒泡排序的规则改了一下，每次循环可以对任意数进行一次冒泡，问最少需要多少次循环
思路：想一下就可以知道只要需要多少的数的右边有比它小的数
直接用一个tmpmin记录当前右边的最小值即可，我用了树状数组就当练习一下
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;const int N=1e6+100 ;int num[N];int n;int tree[N];int lowbit(int x){return x&-x;}int sum(int x){int s=0;for(int i=x;i>=1;i-=lowbit(i)){s+=tree[i];if(s>0) return s;}return s;}void update(int x){for(int i=x;i<N;i+=lowbit(i)){tree[i]++;}}int main(){int T;scanf("%d",&T);for(int cas=1;cas<=T;cas++){memset(tree,0,sizeof(tree));int ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&num[i]);}for(int i=n;i>=1;i–){if(sum(num[i])>0) ans++;update(num[i]);}printf("Case #%d: %d\n",cas,ans);}return 0;}
，你不怕困难，困难就怕你。
