2022.1.28 训练日记 2.acwing.2041. 干草堆

题目链接：干草堆

题目分析：

 0.差分模板题1.由题目可以分析出 首先第一个操作是给[l,r]这个区间上面加1。第二个操作就是输出N个草堆的中位数。1.第一个操作是 经典的差分运用。2.实现第二个操作的方式：2.1 sort排序。排完之后，直接输出a[n / 2 + 1] //为什么+1，因为差分数组下标从1开始。O(nlogn)2.2 nth_element 求第k个数。O(n)nth_element(1,2,3) //一共三个参数1.数组起始位置2.要求的第k个数的位置。3.数组终点位置

code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>using namespace std;const int N = 1000010;int n, m;//长度为n, m次操作
int b[N];//差分数组int main()
{
    scanf("%d%d", &n, &m);while(m --){
    int l, r;scanf("%d%d", &l, &r);b[l] ++, b[r + 1] --;}//求前缀和 得到最终的草堆数 数组。for(int i = 1; i <= n; i ++) b[i] += b[i - 1];//第一种方法//sort(b + 1, b + 1 + n);//第二种方法 nth_elementnth_element(b + 1, b + n / 2 + 1, b + 1 + n);cout << b[n / 2 + 1] << endl;return 0;
}

总结：

1.nth_element()函数总结
1.1 函数参数
nth_element(first, nth, last, compare)
求[first, last]这个区间中第n大小的元素，如果参数加入了compare函数，就按compare函数的方式比较。
1.2 头文件
#include<algorithm>
1.3 作用
nth_element仅排序第n个元素（从0开始索引），即将位置n（从0开始）的元素放在第n大的位置，处理完之后，默认排在它前面的元素都不比它大，排在它后面的元素都不比它小。
例如：    array[first, last)元素区间，排序后，array[nth]就是第n大的元素（从0开始）但是[first, nth) 和 [nth,last)区间的大小顺序不一定。但是可以确定的是array[nth]一定是整个区间里第n大的元素。[first,nth)中的元素都是不大于array[nth]的，[nth, last)中的元素都是不小于array[nth]的。
1.4 nth_element()总结转载于https://blog.csdn.net/xiaoquantouer/article/details/51591140

 2.差分算法总结对于一个给定的序列A，它的差分序列B定义为：B[1] = A[1], B[i] = A[i] - A[i - 1]   (2 <= i <= n)差分和前缀和是一对互逆运算。差分序列B的前缀和序列是原序列A，前缀和序列S的差分序列也是原序列A。操作一：把序列A的区间[l,r]加d。其差分序列变化为：B[i] + d, B[r + 1] - d。其他位置不变。这有助于我们在很多题目中，把原序列上的“区间操作”转化为差分序列上面的“单点操作”以便于降低求解难度。