zjh

用户名：speaksoftly

访问量：24718

签　名：

搞spring去了...不能愉快的刷题了...

等　　级
排　　名	172
经　　验	6955
参赛次数	10
文章发表	37
年　　龄	0
在职情况	学生
学　　校	海南
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1242-网线主管（C++代码）二分
浏览：1468

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （Java代码）

C语言程序设计教程（第三版）课后习题11.8 （Java代码）

蓝桥杯历届试题-小朋友排队（C++代码）线段树O(nlogm)算法

　　作者: zjh　　　　发表时间：2019-08-24 23:33:32 浏览：735　|　评论：0　

原题链接：蓝桥杯历届试题-小朋友排队

```cpp
双倍经验：https://www.lintcode.com/problem/count-of-smaller-number-before-itself/description?_from=ladder&&fromId=26
建议先把上题做完之后再来做此题；

思路：相信看到题目的你第一时间想到的应该是冒泡排序，但是如果冒泡排序的话n <= 1e5 时间复杂度是O(n^2)，这必然会TLE，并且冒泡排序并不能保证移动次数最小。
	我们知道最终从低到高排列，而交换的都是不满足前小后大这一规律，所以我们很容易想到逆序对（i < j && A[i] > A[j])。
	如果能想到逆序对，那么就已经做对一半了。
	小朋友最小交换次数就是该小朋友在（正反逆序对（反：它前面有多少个数大于它； 正：它后面有多少个数小于它））中出现的次数总和，而交换 k 次不高兴程度就增加 k，所以最后每个小朋友的不高兴程度就是 1 ～ k 的累加和。这样只要能统计处该小盆友在所有逆序对
	比如样例（3， 2， 1）
	反逆序对：0，1，2
	正逆序对：2，1，0
	总      和：2，2，2
	最终对每个小朋友的k进行单独的1～k累加就是答案：9
	值得注意（坑点）的是当n = 1e5，并且给定的是一个近乎从大到小排列的顺序， 那么我们每次求累加的时候都会有大量的冗余计算，这会导致TLE(表示被坑了一回...)
所以我们最好的办法是进行一个累加和的打表，从1 ～ 1e6打表，因为最差的情况是A[0] = 1e6 那么它的逆序对总和就是1e6

#include "cstdio"
#include "cstdlib"
#include "iostream"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "map"
#include "vector"
#include "stack"
#include "set"
#include "climits"

using namespace std;

typedef long long ll;
typedef unsigned long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 1000010;

/** 快读 */
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;
}

//tree：线段树结点，lazy：懒标记，A：存各个小朋友升高
int tree[maxn << 2], lazy[maxn << 2], A[maxn], n;
vector<int> B;	//逆序对总和
ll total[maxn];	//累加和打表

void Total() {
    for(int i = 1; i < maxn; ++i) total[i] = total[i - 1] + i;
}

/** 标记下传 */
void push_down(int node, int start, int end) {
    if(lazy[node]) {
        lazy[node << 1] += lazy[node];
        lazy[node << 1 | 1] += lazy[node];
        int mid = (start + end) >> 1;
        tree[node << 1] += (mid - start + 1) * lazy[node];
        tree[node << 1 | 1] += (end - mid) * lazy[node];
        lazy[node] = 0;
    }
}

/** 区间更新
 * node：当前结点
 * start：tree的左区间
 * end：tree的右区间
 * l：更新的左区间
 * r：更新的右区间
 */
void update(int node, int start, int end, int l, int r) {
    if(r < l) return ;
    if(l <= start && r >= end) {
        tree[node] += end - start + 1;
        lazy[node]++;
        return ;
    }
    push_down(node, start, end);
    int mid = (start + end) >> 1;
    if(l <= mid) update(node << 1, start, mid, l, r);
    if(r > mid) update(node << 1 | 1, mid + 1, end, l, r);
    tree[node] = tree[node << 1] + tree[node << 1 | 1];
}

/**
* node：当前结点
* start：tree的左区间
* end：tree的右区间
* p：查找元素的编号
*/
int query(int node, int start, int end, int p) {
    if(start == end) return tree[node];
    push_down(node, start, end);
    int ans = 0;
    int mid = (start + end) >> 1;
    if(p <= mid) ans += query(node << 1, start, mid, p);
    else ans += query(node << 1 | 1, mid + 1, end, p);
    return ans;
}

int main() {
    n = read();
	//因为输入数据里 0 <= Hi <= 1e6，因个人习惯，不喜欢0，所以 + 1，同样的 1 <= Hi <= 1e6 + 1
    for(int i = 0; i < n; ++i) A[i] = read() + 1;
    for(int i = n - 1; i >= 0; --i) {
        B.push_back(query(1, 1, 1e6 + 1, A[i]));	//求该小朋友后面一共有多少个比自己矮的小朋友，注意这里是从最后一个小朋友开始，也就是说B[0]代表最后一位小朋友
        update(1, 1, 1e6 + 1, A[i] + 1, 1e6 + 1);
    }
	//初始化刚才的tree和lazy
    memset(tree, 0, sizeof tree);
    memset(lazy, 0, sizeof lazy);
    for(int i = 0; i < n; ++i) {
        B[n - i - 1] += query(1, 1, 1e6 + 1, A[i]);	//求该小朋友前面有多少个比自己高的小朋友，这里从0开始，所以需要B[n - i - 1]
        update(1, 1, 1e6 + 1, 1, A[i] - 1);
    }
    Total();	//打表
    ll res = 0;
    for(int i = 0; i < n; ++i)
        res += total[B[i]];	//求每个小朋友的不高心值
    printf("%lld\n", res);
    return 0;
}
```

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zjh

TA的其他文章

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （Java代码）

C语言程序设计教程（第三版）课后习题11.8 （Java代码）

Minesweeper （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

蓝桥杯历届试题-小朋友排队（C++代码）线段树O(nlogm)算法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

九宫重排（C++代码）

【排队买票】（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

1118（求助_已解决）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蚂蚁感冒（C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

分糖果（C语言代码）

zjh

TA的其他文章

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （Java代码）

C语言程序设计教程（第三版）课后习题11.8 （Java代码）

Minesweeper （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

蓝桥杯历届试题-小朋友排队 （C++代码）线段树O(nlogm)算法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

九宫重排 （C++代码）

【排队买票】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

1118（求助_已解决）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蚂蚁感冒 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

分糖果 （C语言代码）

蓝桥杯历届试题-小朋友排队（C++代码）线段树O(nlogm)算法

　　评论区

九宫重排（C++代码）

【排队买票】（C语言代码）

蚂蚁感冒（C语言代码）

分糖果（C语言代码）