贝茜对她最近在农场周围造成的一切恶作剧感到抱歉,她同意帮助农夫约翰把一批新到的干草捆堆起来。
开始时,共有 N 个空干草堆,编号 1∼N
。
约翰给贝茜下达了 K 个指令,每条指令的格式为 A B,这意味着贝茜要在 A..B范围内的每个干草堆的顶部添加一个新的干草捆。
例如,如果贝茜收到指令 10 13,则她应在干草堆 10,11,12,13
中各添加一个干草捆。
在贝茜完成了所有指令后,约翰想知道 N 个干草堆的中值高度——也就是说,如果干草堆按照高度从小到大排列,位于中间的干草堆的高度。
方便起见,N 一定是奇数,所以中间堆是唯一的。
请帮助贝茜确定约翰问题的答案。
输入格式
第一行包含 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。
解题思路:
这道题比较模板,学会差分模板题就可做这道题,首先谈谈解题思路,题中说有N个空的干草堆,要往里面放干草捆,其中呢有K个操作是用来放干草捆的,每个操作执行从i到j放一个干草捆,执行完K个操作再对所有的干草堆进行升序排序,最后输出中值,由于题目中说了N是奇数个,所以直接用N/2+1即可得到中值位置,题目中我用到了快速排序和差分,利用差分来做干草捆放置,用快排进行排序
快排模板:
void quick_sort(int a[],int l,int r)
{
if(l>=r)
{
return;
}
int i = l-1;
int j = r+1;
int x = a[l+r>>1];
while(i[HTML_REMOVED]x);
if(i<j) swap(a[i],a[j]);
}
quick_sort(a,l,j);
quick_sort(a,j+1,r);
}
差分模板:
const int N = 1e6+10;
int b[N];
void insert(int l,int r,int c)
{
b[l]+=c;
b[j]-=c;
}
具体代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N];
int b[N];
void quick_sort(int a[],int l,int r)
{
if(l>=r)
{
return;
}
int i = l-1;
int j = r+1;
int x = a[l+r>>1];
while(i[HTML_REMOVED]x);
if(i<j) swap(a[i],a[j]);
}
quick_sort(a,l,j);
quick_sort(a,j+1,r);
}
void insert(int l ,int r)
{
b[l]+=1;
b[r+1]-=1;
}
int main()
{
int l,r;
int n,k;
cin>>n>>k;
for(int i = 0;i[HTML_REMOVED]>l>>r;
insert(l,r);
}
for(int i = 1;i<=n;i++)
{
a[i] = a[i-1]+b[i];
}
quick_sort(a,1,n);
cout<<a[n/2+1]<<endl;
return 0;
}