浇花"/>
M HJ浇花
链接:
来源:牛客网
题目描述
HJ养了很多花(99999999999999999999999999999999999盆),并且喜欢把它们排成一排,编号0~99999999999999999999999999999999998,每天HJ都会给他的花浇水,但是他很奇怪,他会浇n(1 <= n <= 2 * 105)次水,每次都会选择一个区间[l, r],(0 <= l <= r <= 106),表示对区间[l, r]的花都浇一次水。现在问你,通过这些操作之后,被浇了i(1 <= i <= n)次水的花的盆数。
输入描述:
输入:第一行一个n,表示HJ的操作次数,接下来的n行,表示每一次选择的浇水区间。
输出描述:
输出:输出n个数字Cnt1, Cnt2……Cntn,(用空格隔开)Cnti表示被浇了i次水的花的盆数。示例1
输入
复制3 0 3 1 3 3 8
输出
复制6 2 1示例2
输入
复制3 1 3 2 4 5 7
输出
复制5 2 0
说明
对于样例1的图形解释
被浇了1次的有:0, 4, 5, 6, 7, 8, cnt1 = 6
被浇了2次的有:1, 2. cnt2 = 2
被浇了3次的有: 3 . cnt3 = 3
差分一下,挺简单
#include<stdio.h> #include<iostream> using namespace std; int fn[1000000+10]; int c[1000000+10]; int main() {int n;int a,b;scanf("%d",&n);int m = n,max = 0;while(m--){scanf("%d %d",&a,&b); // for(int i = a;i <= b;i++){ // fn[i]++;if(max < b)max = b;++fn[a];--fn[b+1];} //}int maxn = 0;for(int i = 0; i <= max; i++){fn[i] = fn[i] + fn[i-1];c[fn[i]]++;} //for(int i = 0;i < )for(int i = 1; i <= n; i++){printf("%d ",c[i]);}printf("\n"); }View Code
曼哈顿距离 欧几里得距离 切比雪夫距离POJ 2926 Requirements (多维最远曼哈顿距离)
转载于:.html
更多推荐
M HJ浇花
发布评论