前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >洛谷P1966 火柴排队(逆序对)

洛谷P1966 火柴排队(逆序对)

作者头像
attack
发布2018-11-09 16:59:08
4350
发布2018-11-09 16:59:08
举报
文章被收录于专栏:数据结构与算法

题意

题目链接

Sol

不算很难的一道题

首先要保证权值最小,不难想到一种贪心策略,即把两个序列中rank相同的数放到同一个位置

证明也比较trivial。假设\(A\)中有两个元素\(a, b\),\(B\)中有两个元素\(c, d\)

然后分别讨论一下当\(a < b\)时\(c\)与\(a\)对应优还是与\(b\)对应优。

化简的时候直接对两个式子做差。

这样我们找到第二个序列中的每个数应该排到哪个位置,树状数组求一下逆序对就行了。

代码语言:javascript
复制
#include<bits/stdc++.h>
#define lb(x) (x & -x)
#define Fin(x) {freopen(#x".in", "r", stdin);}
using namespace std;
const int MAXN = 1e5 + 10, mod = 99999997;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    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;
}
int N, a[MAXN], b[MAXN], pos[MAXN], rak[MAXN], date[MAXN], T[MAXN];
void Get(int *a) {
    memcpy(date, a, sizeof(a) * (N + 1));
    sort(date + 1, date + N + 1);
    int num = unique(date + 1, date + N + 1) - date - 1;
    for(int i = 1; i <= N; i++) a[i] = lower_bound(date + 1, date + num + 1, a[i]) - date;
}
void Add(int x, int val) {
    while(x <= N) T[x] += val, x += lb(x);
}
int Query(int pos) {
    int ans = 0;
    while(pos) ans += T[pos], pos -= lb(pos);
    return ans;
}
int add(int x, int y) {
    if(x + y < 0) return x + y + mod;
    else return (x + y >= mod) ? x + y - mod : x + y;
}
signed main() {
    N = read();
    for(int i = 1; i <= N; i++) a[i] = read();
    for(int i = 1; i <= N; i++) b[i] = read();
    Get(a); Get(b);
    for(int i = 1; i <= N; i++) pos[a[i]] = i;
    for(int i = 1; i <= N; i++) rak[i] = pos[b[i]];
    int ans = 0;
    for(int i = 1; i <= N; i++) 
        Add(rak[i], 1), ans = add(ans, i - Query(rak[i]));
    printf("%d", ans);
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-10-23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • Sol
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档