P5149 会议座位

超、凢脫俗 2024-04-20 10:32 3阅读 0赞

##  ##

P5149 会议座位

### 题意： ###

> 其实还是求逆序对数。

### 解法： ###

> 用离散化统计每个数，再用树状数组求逆序对。

### CODE： ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> using namespace std; #define LL long long #define N 100010 struct Node { int pos,val; } a[N]; map<string,int> Hash; char ch[10]; int tree[N],n,tag[N]; LL ans; inline bool cmp(Node a,Node b) { if(a.val == b.val) return a.pos < b.pos; return a.val < b.val; } inline int lowbit(int x) { return x & (-x); } inline void add(int x) { for( ; x <= n ; x += lowbit(x)) tree[x]++; return; } inline int query(int x) { int ans = 0; for( ; x ; x -= lowbit(x)) ans += tree[x]; return ans; } int main() { scanf("%d",&n); for(int i = 1 ; i <= n ; i++) { scanf("%s",ch); Hash[ch] = i; } for(int i = 1 ; i <= n ; i++) { scanf("%s",ch); a[i].pos = i; a[i].val = Hash[ch]; } sort(a + 1,a + n + 1,cmp); for(int i = 1 ; i <= n ; i++) tag[a[i].pos] = i; for(int i = n ; i >= 1 ; i--) { ans += query(tag[i]); add(tag[i]); } printf("%lld \n",ans); //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11469800.html

发表评论取消回复

表情：

评论列表（有 0 条评论，3人围观）

还没有评论，来说两句吧...

相关阅读

相关 P5149 会议座位

P5149 会议座位题意： > 其实还是求逆序对数。解法： > 用离散化统计每个数，再用树状数组求逆序对。 CODE： incl...

超、凢脫俗/ 2024年04月20日 10:32/ 0 赞/ 4 阅读

相关视频会议

视频会议系统是一种在位与两个或多个地点的多个用户之间提供语音和运动彩色画面的双向实时传送的视听会话型会议业务。大型视频会议系统在军事、政府、商贸、医疗等部门有广泛的应用。视频会

Bertha 。/ 2022年08月14日 00:58/ 0 赞/ 188 阅读

相关排座位

要安排：3个A国人，3个B国人，3个C国人坐成一排。要求不能使连续的3个人是同一个国籍。求所有不同方案的总数？参考代码： include<std

秒速五厘米/ 2022年08月02日 12:40/ 0 赞/ 92 阅读

相关问题 : 占座位

题目描述 sun所在学校的教室座位每天都是可以预占的。一个人可以去占多个座位，而且一定是要连续的座位，如果占不到他所要求的这么多座位，那么他就一个座位也不要了。为了降

一时失言乱红尘/ 2022年06月10日 07:15/ 0 赞/ 117 阅读

相关国际会议级别

附件是计算机领域的学术会议等级排名情况，分为A+, A, B, C, L 共5个档次。其中A+属于顶级会议，基本是这个领域全世界大牛们参与和关注最多的会议。国内的研究者能在其

电玩女神/ 2022年05月18日 09:29/ 0 赞/ 1626 阅读

相关事后诸葛亮会议

beta 阶段的 postmortem 报告 1. 每个成员在beta 阶段的实践和alpha 阶段有何改进? <table> <tbody> <tr>

迈不过友情╰/ 2021年12月21日 23:57/ 0 赞/ 195 阅读

相关会议2.8

任务看板： ![1659033-20190623041332703-478775088.jpg][] 燃尽图： ![1659033-2019062304134325

骑猪看日落/ 2021年12月21日 06:13/ 0 赞/ 221 阅读

相关会议2.4

任务看板： ![1659033-20190623040901966-1374083027.jpg][] 燃尽图： ![1659033-201906230409203

怼烎@/ 2021年12月21日 06:13/ 0 赞/ 213 阅读

相关会议1.4

任务看板： ![1659033-20190528155732206-2136703787.png][] 燃尽图： ![1659033-20190528162740180-

た入场券/ 2021年12月21日 06:11/ 0 赞/ 226 阅读

相关多方会议会议解决方案

使用腾讯云的实时音视频功能主要是基于小程序和安卓和IOS 解决问题 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk

ゝ一世哀愁。/ 2021年08月29日 18:04/ 0 赞/ 348 阅读