acwing-2041. 干草堆(acwing-2041. Haystack)

贝茜对她最近在农场周围造成的一切恶作剧感到抱歉,她同意帮助农夫约翰把一批新到的干草捆堆起来。
开始时,共有 N 个空干草堆,编号 1N。
约翰给贝茜下达了 KK 个指令,每条指令的格式为 ,这意味着贝茜要在 A..B 范围内的每个干草堆的顶部添加一个新的干草捆。
例如,如果贝茜收到指令 ,则她应在干草堆 10,11,12,13 中各添加一个干草捆。
在贝茜完成了所有指令后,约翰想知道 NN 个干草堆的中值高度——也就是说,如果干草堆按照高度从小到大排列,位于中间的干草堆的高度。
方便起见,N 一定是奇数,所以中间堆是唯一的。
请帮助贝茜确定约翰问题的答案。

A B
10 13

输入格式

第一行包含 N 和 K。
接下来 K 行,每行包含两个整数 A,B,用来描述一个指令。

输出格式

输出完成所有指令后,N 个干草堆的中值高度。

数据范围

1≤N≤106,
1≤K≤25000,
1≤A≤B≤N

输入样例:

7 4
5 5
2 4
4 6
3 5

输出样例:

1

样例解释

贝茜完成所有指令后,各堆高度为 0,1,2,3,3,1,0。
将各高度从小到大排序后,得到 0,0,1,1,2,3,3,位于中间的是 1

方法一:暴力(TLE)

对区间内所有元素++,最后找中位数的findMid使用的是快排思想(也是std::nth_element找第k个大的数的思想)

最后运行超时,而且不知道对不对

#include <bits/stdc++.h>
using namespace std;
int findMid(int* nums, int low, int high, int mid) {
    int pivot = nums[low];
    int l = low, h = high;
    while (low < high) {
        while (low < high && nums[high] >= pivot) high--;
        nums[low] = nums[high];
        while (low < high && nums[low] <= pivot) low++;
        nums[high] = nums[low];
    }
    nums[low] = pivot;
    if (low == mid) return pivot;
    else if (low < mid) return findMid(nums, low+1, h, mid);
    else return findMid(nums, l, low-1, mid);
}

//1 2 3 4 5 6 7

int main() {
    int n, k, a, b;
    scanf("%d%d", &n, &k);
    int *nums =  new int[n+1];
    memset(nums, 0, sizeof(int) * (n+1));
    for (int i = 0; i < k; ++i) {
        scanf("%d%d", &a, &b);
        for (int j = a; j <= b; ++j) {
            nums[j]++;
        }
    }

    printf("%d", findMid(nums, 1, n, (1+n)/2));
    delete []nums;
}

方法二:差分数组

差分数组模板题了属于是

#include <bits/stdc++.h>
using namespace std;
int d[1000010];
int main() {
    int n, k, a, b;
    scanf("%d%d", &n, &k);
    while (k--) {
        scanf("%d%d", &a, &b);
        d[a-1]++; d[b]--; // 差分数组
    }
    for (int i = 1; i < n; i++) d[i] += d[i-1];
    nth_element(d, d+n/2, d+n);
    printf("%d", d[n/2]);
}
————————

Bessie was sorry for all the mischief she had caused around the farm recently. She agreed to help farmer John pile up a new batch of hay.
At the beginning, there were n empty haystacks numbered 1n.
John gave Bessie KK instructions. The format of each instruction is, which means that Bessie has to be in a Add a new hay bale at the top of each haystack in range B.
For example, if Bessie receives a command, she should add one hay bale to each of the hay piles 10, 11, 12, and 13.
After Bessie finished all the instructions, John wanted to know the median height of NN haystacks – that is, if the haystacks were arranged from small to large, the height of the haystack in the middle.
For convenience, n must be odd, so the middle heap is unique.
Please help Bessie determine the answer to John’s question.

A B
10 13

Input format

The first line contains n and K.
Next, line k contains two integers a and B to describe an instruction.

Output format

The median height of N haystacks after all instructions are output.

Data range

1≤N≤106,
1≤K≤25000,
1≤A≤B≤N

Input example:

7 4
5 5
2 4
4 6
3 5

Output example:

1

Example explanation

After Bessie completes all instructions, the height of each heap is 0,1,2,3,3,1,0.
After sorting the heights from small to large, 0,0,1,1,2,3,3 is obtained, and 1 is in the middle

Method 1: violence (TLE)

For all elements + + in the interval, the idea of fast sorting is used to find the median findmid (also the idea of STD:: nth_element finding the k-th largest number)

Finally, the operation timed out, and I don’t know if it’s right

#include <bits/stdc++.h>
using namespace std;
int findMid(int* nums, int low, int high, int mid) {
    int pivot = nums[low];
    int l = low, h = high;
    while (low < high) {
        while (low < high && nums[high] >= pivot) high--;
        nums[low] = nums[high];
        while (low < high && nums[low] <= pivot) low++;
        nums[high] = nums[low];
    }
    nums[low] = pivot;
    if (low == mid) return pivot;
    else if (low < mid) return findMid(nums, low+1, h, mid);
    else return findMid(nums, l, low-1, mid);
}

//1 2 3 4 5 6 7

int main() {
    int n, k, a, b;
    scanf("%d%d", &n, &k);
    int *nums =  new int[n+1];
    memset(nums, 0, sizeof(int) * (n+1));
    for (int i = 0; i < k; ++i) {
        scanf("%d%d", &a, &b);
        for (int j = a; j <= b; ++j) {
            nums[j]++;
        }
    }

    printf("%d", findMid(nums, 1, n, (1+n)/2));
    delete []nums;
}

Method 2: differential array

The difference array template problem belongs to yes

#include <bits/stdc++.h>
using namespace std;
int d[1000010];
int main() {
    int n, k, a, b;
    scanf("%d%d", &n, &k);
    while (k--) {
        scanf("%d%d", &a, &b);
        d[a-1]++; d[b]--; // 差分数组
    }
    for (int i = 1; i < n; i++) d[i] += d[i-1];
    nth_element(d, d+n/2, d+n);
    printf("%d", d[n/2]);
}