BNU 4096 逆序思维题

https://www.bnuoj.com/v3/problem_show.php?pid=4096

对于一个序列a，我们定义它的逆序数为满足a[i]>a[j]且i<j的有序对<i,j>的个数，这样的有序对称为逆序对。

例如 a[0]=1，a[1]=2，a[2]=4，a[3]=5，a[4]=3，存在的逆序对就有<2,4>和<3,4>，其逆序数就是2。

现在，给你一个长为N的序列，要求恰好执行K次交换操作，每次交换只能在相邻的两个数之间进行，问得到的结果序列其逆序数最小和最大可能是多少。

Input

输入数据有多组，每组数据包括两行，第一行有两个整数N (1<=N<=1,000)和K(0<=K<=1,000,000,000)，分别是序列的长度和需要执行的交换操作的次数。

第二行有N个整数，依次给出了序列中的所有数，都在int范围内。

输入以EOF结束。

Output

对于每组数据，单独输出一行，包括两个整数，以一个空格隔开，第一个为执行恰好K次操作后得到的最小逆序值，第二个为最大逆序值。

Sample Input

Sample Output

1 1

0 2

Source

2009年北京师范大学新生程序设计竞赛正式赛

Author

Huang Kun @ BNU (modified from HUST campus)

这个关键在于想到

1、有重复数字

2、逆序对数目最大不一定是 n * (n - 1) / 2的，因为有重复数字的话，2、2、2这样的数据，就是0

我的思路是先求出一开始的逆序对数目，然后和k比较，因为它能移k次，按照最优的方案来说，每次都能增加/减去1个逆序对数目。

所以判断下当前有多少个逆序对now + k 和mx的关系即可

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

int n, k;

const int maxn =  + ;

int a[maxn];

int b[maxn];

map<int, int>book;

int calc(int a[]) {

    int ans = ;

    for (int i = ; i <= n; ++i) {

        for (int j = i + ; j <= n; ++j) {

            if (a[i] > a[j]) ++ans;

        }

    }

    return ans;

}

bool cmp(int a, int b) {

    return a > b;

}

void work() {

    int bug = ;

    book.clear();

    for (int i = ; i <= n; ++i) {

        scanf("%d", &a[i]);

        b[i] = a[i];

        if (book[a[i]]) bug = ;

        book[a[i]]++;

    }

    int now = calc(a);

    sort(a + , a +  + n, cmp);

    int mx = calc(a);

    int ansmi = ;

    int ansmx = ;

    int mxcut = , miadd = ;

    if (n == ) {

        printf("0 0\n");

        return;

    }

    if (now + k <= mx) {

        ansmx = now + k;

    } else {

        ansmx = mx;

        int left = now + k - mx;

        if (left %  ==  && !bug) mxcut = ;

    }

    if (now - k >= ) {

        ansmi = now - k;

    } else {

        ansmi = ;

        int left = k - now;

        if (left %  ==  && !bug) miadd = ;

    }

    printf("%d %d\n", ansmi + miadd, ansmx - mxcut);

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    while (scanf("%d%d", &n, &k) != EOF) work();

    return ;

}

逆序