# acwing-2041. 干草堆(acwing-2041. Haystack)-其他

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

``A B``
``10 13``

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

### 输入样例：

``````7 4
5 5
2 4
4 6
3 5
``````

### 输出样例：

``````1
``````

### 方法一：暴力（TLE）

``````#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.

``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.

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]);
}
``````