原题链接：蓝桥杯历届试题-小朋友排队
解题思路:
这道题最终要求解的其实就是给定整数串中的逆序对的个数，但此题直接暴力是会超时的，所以利用树状数组进行求解，思路如下：首先利用输入的整数串构建一个树状数组，然后树状数组的getSum()可以求解从1开始的一些项的和，如果按顺序输入的话，就可以求解当前输入项之前比它矮的小朋友个数，而且也知道已经输入了多少个小朋友的身高，那么很自然可以求出大于等于当前身高的小朋友个数，但是还存在身高相等的情况，需要减去等于当前身高的个数，也就是getSum(i+1)-getSum(i)，存入一个数组，然后，再从尾开始遍历，也可以用同样的方法，求取身高小于当前身高的小朋友个数，然后与之前的大于的对应相加，即可求得对于每一个身高，其逆序对的个数，最后将其全部加起来即是最终结果。
注意事项:
1. 要注意爆int，对于不高兴度，当交换次数很大的时候是会爆int的。
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include <iostream>#include <cstring>#define maxn 100010#define MAXH 1000010using namespace std;long long total[maxn];int c1[MAXH], c2[MAXH];int num[maxn];int cou[MAXH];int n;void init() { total[0] = 0; for (int i = 1; i <= maxn; i++) { total[i] = total[i - 1] + i; }}int lowbit(int x) { return x & (-x);}void update(int pos, int val, int* c) { while (pos <= MAXH) { c[pos] += val; pos += lowbit(pos); }}int getSum(int pos, int* c) { int ans = 0; while (pos > 0) { ans += c[pos]; pos -= lowbit(pos); } return ans;}int main() { init(); while (cin >> n) { memset(c1, 0, sizeof(c1)); memset(c2, 0, sizeof(c2)); memset(cou, 0, sizeof(cou)); for (int i = 1; i <= n; i++) { cin >> num[i]; update(num[i] + 1, 1, c1); cou[i] = i - getSum(num[i], c1); cou[i] -= (getSum(num[i] + 1, c1) - getSum(num[i], c1)); } for (int i = n; i > 0; i--) { update(num[i] + 1, 1, c2); cou[i] += getSum(num[i], c2); } long long ans = 0; for (int i = 1; i <= n; i++) { ans += total[cou[i]]; } cout << ans << endl; } return 0;} |
7 分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复