- #include<bits/stdc++.h>
- using namespace std;
- int f(int n){
- int num=0;
- for(int i=1;i<=n;i++){
- num+=i;
- }
- return num;
- }
- int main()
- {
- int array[100000];
- memset(array,0,sizeof(array));
- int array1[100000];
- memset(array1,0,sizeof(array1));
- int n;
- cin>> n;
- for(int i=0;i<n;i++){
- cin>> array[i];
- }
- for(int i=0;i<n;i++){
- for(int j=0;j<n;j++){
- if(j<i){
- if(array[j]>array[i]){
- array1[i]++;
- }
- }
- if(j>i){
- if(array[j]<array[i]){
- array1[i]++;
- }
- }
- }
- }
- int all=0;
- for(int i=0;i<n;i++){
- all+=f(array1[i]);
- }
- cout <<all << endl;
- return 0;
- }
运行结果部分数据超时. 考虑到用快排做每个对象交换次数, 但是每个位置所指的人是不断变化的, 百度后, 可以考虑使用树状数组,
我也是花了比较长的时间才把树状数组搞懂, 参考博客可以这些, 按顺序看可以理解的更快一些,
- https://blog.csdn.net/Small_Orange_glory/article/details/81290634
- http://www.cnblogs.com/zhangshu/archive/2011/08/16/2141396.html
- https://www.jianshu.com/p/8a4081f0ec20
看完这些博客基本了解了大概, 但是脑子里可能没有直观的印象, 可以根据下面的代码继续理解树状数组在求和, 求前逆序和后逆序. 把代码看懂就算基本入门了树状数组.
- #include<stdio.h>
- #include<string.h>
- #define SIZE1000000+10
- #define N 100000+10
- int allHigh[SIZE]; // 记录每个身高的人数 题目要求最大为 1000000 这里为了防止溢出加多了 10
- int C[SIZE]; // 上面的链接讲树状数组 很清晰, c[n]=a(n-a^k+1)+.........+an (其中 k 为 n 的二进制表示中从右往左数的 0 的个数)
- long long b[N]; // 记录每个人的前逆序对 + 后逆序对
- int n;
- long long judge[N]; // 可以发现不高兴程度 a(n) - a(n-1) ,a(n-1) - a(n-2),... ,a(1) - a(0) 是是一个等差数列, 这里把它们的结果记录在 judge 这个数组里
- int lowbit(int x){ // 求解 a^k
- return x & (-x);
- }
- void add (int i, intx) { // 当数组中的元素有变更时 (这里是增加), 树状数组会高效的计算
- while(i <= SIZE){
- C[i] += x;// 更新 , 统计各个身高段的人数
- i += lowbit(i);
- }
- }
- int sum (int end){ // 求数组的和 , 这时求得是 a[end] 左边被加进来的孩子, 已经规定左边的孩子个子都比 end 小
- int re = 0;
- while(end> 0) {
- re += C[end];
- end -= lowbit(end);
- }
- return re;
- }
- void fun () { // 解决问题
- int i;
- for(i = 0; i <n; i ++){ // 遍历所以小朋友
- scanf("%d",&allHigh[i]);
- add(allHigh[i] + 1, 1); // allHigh 里 对刚获取的值小朋友的身高 的人数加一
- b[i] = (i+1) - sum(allHigh[i]+1); // 统计该小朋友 b[i] 的前逆序对, 因为 sum(allHigh[i]+1) 是求身高比 i 小的小孩且已经加进来的总个数,
- }
- memset(C, 0, sizeof(C)); // 接下来要计算各个人的后逆序对需要吧 C[] 清空
- for(i = n - 1; i>= 0; i --) { // 遍历所以小朋友
- add(allHigh[i] + 1, 1);
- b[i] += sum(allHigh[i]); // 统计该小朋友 b[i] 的前逆序对 + 后逆序对, 后加进来, 且个子比 i 小的孩子为 sum(allHigh[i])
- }
- long long ans = 0
- for(i = 0; i < n; i ++){ // 累加不高兴值
- ans += judge[b[i]]; // 调用之前已经计算好的等差数列数组
- }
- printf("%lld", ans);
- }
- int main () {
- int i;
- scanf("%d", &n);
- memset(allHigh, 0, sizeof(allHigh)); // 初始化
- memset(C, 0, sizeof(C));
- memset(b, 0, sizeof(b));
- judge[0] = 0;
- for(i = 0; i < N; i ++){ //a(n) - a(n-1) ,a(n-1) - a(n-2),... ,a(1) - a(0) 是等差数列
- judge[i] = judge[i - 1] + i;
- }
- fun ();
- return 0;
- }
真的感觉那些发现这些规律, 提出这些算法的人真的太聪明了.
来源: http://www.bubuko.com/infodetail-2995355.html