堆禾草

堆禾草

大致题意：

Time Limit: 1000/500 MS (Java/Others)

一开始有N ( 1 ≤ N ≤ 1000000, N 是奇数 )个空草堆，分别编号为1，2，…，N。现有K个指令，指令的格式是"A B"，表示从编号A到编号B都分别叠加上一堆干禾草，例如，接到指令"10 13"，那么就为草堆10、11、12、13各叠加上一捆禾草。当根据指令完成工作后，计算N堆草的高度的中位数。
Input
有多个测试用例，第一行是一个整数T，表示测试用例的个数。

每个测试用例的第一行是两个整数 N 和 K。第二行开始共K行，每行是两个整数A和B ( 1 ≤ A ≤ B ≤ N )，表示一条指令。

Output
为每个测试用例输出一行结果：完成指令后的各草堆高度的中位数。

Sample Input
1
7 4
5 5
2 4
4 6
3 5

Sample Output
1

Hint
共有7个堆，4条指令。第一条指令是在第5号堆叠加一捆禾草，第二条指令是在第2、3、4号堆上都叠加一捆禾草，如此类推。

完成所有指令后，各草堆的高度是0，1，2，3，3，1，0。草堆的中位数是1，因为按高度排序后的草堆分别是0，0，1，1，2，3，3，中位数是1。

/*两层for暴力计算各堆高度，超时，Time Limit Exceeded*/
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long ll;
using namespace std;
ll qq[1000005];
int main()
{int T,a,b;scanf("%d",&T);while(T--){memset(qq,0,sizeof(qq));int N,K;scanf("%d%d",&N,&K);for(int i=1;i<=K;i++){scanf("%d%d",&a,&b);for(int j=a;j<=b;j++){qq[j]++;}}int w=N/2+1;partial_sort(qq+1,qq+w+1,qq+N+1);printf("%lld\n",qq[w]);}return 0;
}

/*AC249ms*/
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long ll;
const int MAX=1000010;
using namespace std;
ll qq[MAX],z[MAX],y[MAX];
int main()
{int T,a,b;scanf("%d",&T);while(T--){memset(qq,0,sizeof(qq));memset(y,0,sizeof(y));memset(z,0,sizeof(z));int N,K;scanf("%d%d",&N,&K);for(int i=1;i<=K;i++){scanf("%d%d",&a,&b);z[a]++,y[b]++;}ll sum=0;for(int j=1;j<=N;j++){sum+=z[j];qq[j]=sum;sum-=y[j];}/*for(int d=1;d<=N;d++){printf("%lld ",qq[d]);}puts("");*/int w=N/2+1;partial_sort(qq+1,qq+w+1,qq+N+1);printf("%lld\n",qq[w]);}return 0;
}