USACO2012 Haybale stacking区间表示法 oj21556

题目大意：N个方块 标号1~N  K个操作 操作a b 表示标号a~b区间每位多加一个方块 Input

* Line 1: Two space-separated integers, N  K.

* Lines 2..1+K: Each line contains one of FJ's instructions in the form of two space-separated integers A  B (1 ≤ A ≤ B≤ N).

Output

* Line 1: The median height of a stack after Bessie completes the instructions.

Sample Input

7 45 52 44 63 5

Sample Output

1

 

即 有N = 7个方块，发出K = 4个指令。第一条指令是添加方块在堆栈5，第二个是添加方块到堆栈2..4等

输出细节：

操作完成后，堆栈的高度为 0, 1, 2, 3, 3, 1, 0。

中间堆栈高度为1，因为1是排序的顺序中的0, 0, 1, 1, 2, 3, 3。

 

区间表示法

#include <stdio.h> #include <string.h> #include <algorithm> int flag[1000000]={0}; using namespace std; int main() { int n,k; scanf("%d%d",&n,&k); while(k--) { int a,b; scanf("%d%d",&a,&b); flag[a]++; flag[b+1]--; } int sum=0; for(int i=0;i<=n;i++) { sum+=flag[i]; flag[i]=sum; } sort(flag,flag+n+1); printf("%d\n",flag[n/2+1]); return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/8321466.html