【日常学习】【其他算法】codevs3371 刮油漆题解

阳光穿透心脏的1/2处 2022-08-05 08:59 149阅读 0赞

题目描述 Description

小J有一把尺子。一天MPS闲得无聊，拿了一桶油漆，用刷子在上面刷了N下，刷第i次有一个正整数范围(ai，bi)，表示从尺子的刻度ai刷到刻度bi。此时ai到bi这个区间里的油漆层数+1。

为了去掉这些油漆，小J找来了一把刀，每次可以从尺子的一个整数刻度刮到另一个整数刻度。每刮一刀都有一个力度，如力度为3时可以一次刮掉3层油漆。但不能损坏尺子。比如有2层油漆的地方就不能用力度3来刮。

小J想知道最少要刮多少次。

输入描述 Input Description

第一行，一个整数N

第2...N+1行，第i+1行两个整数ai，bi。

输出描述 Output Description

一行，最少刮多少次。

样例输入 Sample Input

3

1 4

2 5

1 5

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

【样例解释】

刮2刀，第一次刮区间(1,5)，力度为2，第一次刮区间(2,4)，力度为1。

【数据范围】

40%的数据N<=2000

100%的数据N,ai,bi<=10^5

乍一看似乎有些复杂，只是好像和“积木大赛”有点像？不同点在于积木大赛只能动一层，而这个可移动很多层。只要是连续区间即可。

于是按照积木大赛的算法改了一下，但是失败了···

但是和正确的算法也有异曲同工之妙

事实上，我们只需要在读入每个区间时【对区间的左端点a\[k\]+1，右端点a\[k\]-1，最后统计是正数多还是负数多即可】

为什么这样可以呢？我们举一个例子：

第一个区间【1,3】

第二个区间【1,5】

那么图像是这样的

XXX

XXXXX

对应数字为

1 0 -1 0 -1

结合积木大赛的思路，由于负数有两个，有两处下降，那么至少两次才能刮完。更多情况，可以以此深入理解。

code

//codevs3371 刮油漆
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=500000+10;
    int p[maxn]; 
    int n;
    
    int main()
    {
    	scanf("%d",&n);
    	int a,b;
    	for (int i=1;i<=n;i++)
    	{
    		scanf("%d%d",&a,&b);
    		p[a]++;
    		p[b]--;
    	}
    	int po=0,ne=0;
    	for (int i=1;i<=maxn-9;i++)
    	{
    		if (p[i]>0) po++;
    		if (p[i]<0) ne++;
    	}
    	if (po>ne) printf("%d\n",po);
    	else printf("%d\n",ne);
    	return 0;
    }

——泪随流水急，愁逐野云飞

发表评论取消回复

表情：

评论列表（有 0 条评论，149人围观）

还没有评论，来说两句吧...

相关阅读

相关【日常学习】【数学】codevs3625 士兵站队问题题解

题目描述 Description 在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点用整数坐标(x,y)表示。士兵们可以沿网格边往上、下、左、右移动一步，但在同一时

深碍√TFBOYSˉ_/ 2022年08月09日 14:49/ 0 赞/ 261 阅读

相关【日常学习】【其他算法】codevs3371 刮油漆题解

题目描述 Description 小J有一把尺子。一天MPS闲得无聊，拿了一桶油漆，用刷子在上面刷了N下，刷第i次有一个正整数范围(ai，bi)，表示从尺子的刻度ai刷到刻度

阳光穿透心脏的1/2处/ 2022年08月05日 08:59/ 0 赞/ 150 阅读

相关【日常学习】codevs1294 全排列题解

惊奇的发现我竟然没写过这个粘了黄学长的代码因为所有的递归全排列拥有共同的灵魂我经常犯得错误是把取消标记放到循环外至今没开博的查查比君纠正过很多次所以记住

╰半夏微凉°/ 2022年08月04日 16:45/ 0 赞/ 251 阅读

相关【日常学习】【IDA*】codevs2449 骑士精神题解

题目描述 Description 在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐

布满荆棘的人生/ 2022年08月04日 05:17/ 0 赞/ 182 阅读

相关【日常学习】【区间DP】codevs1048 石子归并题解

题目描述 Description 有n堆石子排成一列，每堆石子有一个重量w\[i\], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w\[i\]+w\[i

迈不过友情╰/ 2022年08月03日 14:47/ 0 赞/ 185 阅读

相关【日常学习】【背包DP】codevs1014 装箱问题题解

转载请注明出处来自CSDN用户ametake 题目来自NOIP2011PJ4 上题目题目描述 Description 有一个箱子容量为V（正整数，0＜＝

以你之姓@/ 2022年08月03日 13:41/ 0 赞/ 164 阅读

相关【日常学习】codevs1287 矩阵乘法题解

转载请注明出处 \[ametake版权所有\]http://blog.csdn.net/ametake欢迎来看、先上题目题目描述 Description 小明最近在为

水深无声/ 2022年08月02日 15:43/ 0 赞/ 321 阅读

相关【日常学习】【读入优化】codevs2555 a+b=？题解

题目很简单题目描述 Description 做了，简单的a，b和的问题。但是，如果要求输入的情况不是a和b，而是整个加法表达式呢？请想办法，计算加法表达式的结果。

你的名字/ 2022年08月02日 07:09/ 0 赞/ 111 阅读

相关【日常学习】【深搜】codevs2452 扫雷题解

题目来源：05年四川省选转载请注明出处 \[ametake版权所有\]http://blog.csdn.net/ametake欢迎来看题目描述 Descript

野性酷女/ 2022年08月02日 06:56/ 0 赞/ 163 阅读

相关【日常学习】【线性DP】codevs1044 拦截导弹题解

题目描述 Description 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每

- 日理万妓/ 2022年08月01日 11:27/ 0 赞/ 150 阅读