【排序】逆序对IV

问题 D: 【排序】逆序对IV

时间限制: 1 Sec 内存限制: 128 MB
提交: 20 解决: 15
[提交] [状态] [讨论版] [命题人:]

题目描述

“装满了鹅卵石的瓶子是满的吗？”墨老师曾经这样问过他的学生。“不是，因为还可以放入小石子、再放入细砂、最后再倒入水。”学生们回答。“那么从中可以得到什么启示呢？”墨老师又问，“启示我们时间总是可以挤出来的！”一个聪明的学生抢答。“你说得对！”墨老师微笑道，“但我还要告诉你们另一个重要经验，那就是：如果你不先将大的鹅卵石放进瓶子里去，你也许以后永远没机会再把它们放进去了。”

但这世上的很多人，做事却经常分不清事情的轻重缓急。我们可爱的典狱长大人就犯了这个错误，当他看到身高参差不齐的狱警们排成一列时，眉毛拧成了一个结，他最想知道的就是，到底有多少个狱警逆序排队了。这可以抽象为求逆序对的个数问题：即对于一个包含n个非负整数的数组A[1，…，n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ，A[ j] )为数组A中的一个逆序对。

例如，数组（3，1，4，5，2）的逆序对有(3，1)，(3，2)，(4，2)，(5，2)共4个。

输入

包括两行，第一行是一个整数n(1≤n≤1000)，表示狱警人数。第二行包含n个整数，用空格分隔，即每个狱警的身高，狱警身高均在int范围内。

输出

包括一行，这一行只包含一个整数，即逆序对的个数。

样例输入

5
3 1 4 5 2

样例输出

分析：不懂为什么要排序，这数据才1000，暴力算O(n^2)也不可能超时。。

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#define range(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
#define rerange(i,a,b) for(int i=a;i>=b;--i)
#define fill(arr,tmp) memset(arr,tmp,sizeof(arr))
using namespace std;
int n,num[1005];
void init(){
    cin>>n;
    range(i,1,n)cin>>num[i];
}
void solve(){
    LL ans=0;
    range(i,1,n-1)range(j,i+1,n)if(num[i]>num[j])++ans;
    cout<<ans<<endl;
}
int main() {
    init();
    solve();
    return 0;
}

View Code