题目地址 (萌新第一篇博客,有不对请指正!!)

题目描述:

riba2534不小心穿越到了异世界,他必须从异世界出来,但是异世界有一个大魔王,非得让riba2534回答出他的问题才让他回到地球,问题是这样的:

大魔王用魔法变出来了n座大山,并且告诉你这n座大山的高度,现在他想问你,对于给出的每一座大山,这座大山之前有多少座大山比他的高度低。

riba2534非常惊慌失措,所以请你救救他!

输入描述:

多组测试数据 第一行给出一个整数n(1<=n<=100000)代表有n座大山
第二行给出来每座大山的高度h(1<=h<=1000000000),以空格作为分割。

输出描述:

对于每组数据,输出一行。 代表每座大山之前有多少座大山比这座大山低

思路

刚看这题的时侯天真的用两个for循环,果然TLE了。后面学完树状数组的时侯感觉可以做。看到山的高度那么大脑子里突然蹦出离散化,一直都听过,但是没有看过怎么实现。也算是第一次自己想出自认为有点难度的题目,感觉看别人的代码看多了失去的独立思考的能力。也算是给我敲响了警钟。废话不多说,具体的做法都写在注释里。(看了第一的代码,归并确实可以做,最近比较忙,先刷点别的题再来学习)

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 5;
int c[N], n;//考虑到山的高度会很大,但是并没有什么用,只需要他们的相对大小就可以,所以要离散化处理。
struct mom{
  int id, hight, cs;//id用于离散化, cs用于记录重复的数
}a[N];
bool cmp(const mom &c, const mom & b) {//离散化之后排回去
  return c.id < b.id;
}
bool cmp1(const mom &c, const mom & b) {//按照高度排序,方便进行离散化(ps:离散化方法可能不正规,没去看,然后也懒得改了)
  if(c.hight != b.hight) 
    return c.hight < b.hight;//依稀记得好像快排是不稳定的排序,还是多写个条件,保险!
  return c.id < b.id;
}
//下面三个都是树状数组的常规函数
int lowbit(int x) {
  return x & (-x);
}
void Add(int x) {
  while (x <= n) {
    c[x] += 1;
    x += lowbit(x);
  }
}
int Sum(int x) {
  int sum = 0;
  while(x) {
    sum += c[x];
    x -= lowbit(x);
  }
  return sum;
}
void lsh() {//此处为离散化,我的理解是把高度改成序号就可以,当然,我们要记录重复的,因为不包括相等的!
  int num = a[0].hight;
  a[0].hight = 0;
  for (int i = 1; i < n; i++) {
    if(a[i].hight == num) {
      a[i].hight = a[i-1].hight;
      a[i].cs = a[i-1].cs + 1;
    }
    else {
      num = a[i].hight;
      a[i].hight = i;
    }
  }
}
int main() {
  while(cin >> n) {
    memset(c, 0, sizeof(c));
    for (int i = 0; i < n; i++) {
      cin >> a[i].hight;
      a[i].cs = 0;
      a[i].id = i;
    }
    sort(a, a+n, cmp1);
    lsh();
    sort(a, a+n, cmp);
    for (int i = 0; i < n; i++) {
      cout << Sum(a[i].hight + 1) - a[i].cs;//先求前面有多少个比他小,再把它加入进去。
      if(i < n-1) cout << " " ;
      Add(a[i].hight+1);
    }
    cout << endl; 
  }
}

若有什么不理解,或者不对的地方,欢迎评论!
填坑,比较好的离散化技巧

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int c[N], n;
int lowbit(int x) {
  return x & (-x);
}
void Add(int x) {
  while (x <= n) {
    c[x] += 1;
    x += lowbit(x);
  }
}
int Sum(int x) {
  int sum = 0;
  x--;
  while(x) {
    sum += c[x];
    x -= lowbit(x);
  }
  return sum;
}
//新的离散化方式 
int a[N];
vector<int>v; 
int getid(int x) {
  return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; 
}
int main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  while(cin >> n) {
    v.clear();
    memset(c, 0, sizeof(c));
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      v.push_back(a[i]);
    }
    //下面三行为离散化方式 
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i = 0; i < n; i++) a[i] = getid(a[i]);
    for (int i = 0; i < n; i++) {
      cout << Sum(a[i]);
      if(i < n-1) cout << " " ;
      Add(a[i]);
    }
    cout << endl; 
  }
}