luogu P1966 火柴排队 (逆序对)

luogu P1966 火柴排队

题目链接:https://www.luogu.org/problemnew/show/P1966

显然贪心的想,排名一样的数相减是最优的.

证明也很简单.

此处就不证明了.

然后交换的话就是求一个逆序对.

怎么样排序是一个关键.

\(c\)数组的下标是\(a\)的排名,值是\(b\)的值.

这样求逆序对的时候,就是排名为\(i\)的\(a\)数组,会对应上相应排名的\(b\)数组的上.

这也算是一个小技巧吧.

#include <algorithm>

#include <iostream>

#include <cstdio>

using namespace std;

const int maxN = 100000 + 7;

const int mod = 99999997;

int n;

int f[maxN];

struct Node {

	int id,w;

}a[maxN],b[maxN];

int c[maxN];

int ans;

inline int read() {

	int x = 0,f = 1;char c = getchar();

	while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}

	while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}

	return x * f;

}

bool cmp(Node a,Node b) {

	return a.w < b.w;

}

inline int lowbit(int x) {return x & -x;}

void modify(int pos,int val) {

    while(pos <= n) f[pos] += val,pos += lowbit(pos);

}

int query(int pos) {

    int sum = 0;

    while(pos) sum += f[pos],pos -= lowbit(pos);

    return sum;

}

void re_pair1() {

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

		modify(c[i],1);

		ans += query(n) - query(c[i]);

		ans %= mod;

	}

	printf("%d", ans);

	return ;

}

int main() {

	n = read();

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

		a[i].id = i,a[i].w = read();

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

		b[i].id = i,b[i].w = read();

	sort(b + 1,b + n + 1,cmp);

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

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

		c[a[i].id] = b[i].id;

	re_pair1();

	return 0;

}