计算思维综合训练_2020_07_06

Problem J. sqy 的锡纸烫
时间限制 1000 ms
内存限制 64 MB

题目描述
渣男锡纸烫！

前不久 sqy 老师花了大价钱，去做了一个帅气的锡纸烫。有着商业眼光的 sqy 一下子发现了大商机，于是他自己开了一家美容美发店。

sqy 找了刚刚做完纹理烫的大预言家 cbj 预测了未来，发现每个顾客都只在白天来美发店，并且第一次来店里的时候都会充一次价值 xi 的卡，然后从第二天开始，每天白天都会来这里打理头发，而 sqy 仅收取成本价 1 元钱来吸引顾客，直到把卡掏空为止，这个顾客就再也不会回来。

黑心商人 sqy 找大预言家要来了每个顾客的充卡时间和充值金额，他准备在某一天晚上跑路，他想知道自己最多能卷走多少钱。

输入数据
第一行包括一个整数 n(1≤n≤1e5) 表示有 n 个顾客。 接下来共 n 行，每i+1行包括两个整数 xi,yi 表示第 xi 天一个顾客来充值了 yi 元 (1≤xi≤1e6,0≤yi≤231−1)。

输出数据
输出一行包括一个整数 ans，表示 sqy 最多能卷走多少钱。

样例输入
5
1 5
2 5
3 5
4 5
5 5
样例输出
15
样例说明
在第五天的时候，第一个人消费4元还剩1元，第二个人消费3元还剩2元，第三个人消费2元还剩3元，第四个人消费1元还剩4元，第五个人还没有开始消费就被卷钱跑路了。

---

算法
差分

首先介绍一下朴素的差分。
我们有n个数，m个操作。设0<=n,m<=1e5。n个数和m个操作在读入中给出。m个操作的形式为三个正整数 l r x，表示将这n个数中的第l个到第r个都分别加上x。然后有n次询问，询问第p到第q个数之间所有数字的和为多少？

比如当n=5,m=3
原数列:
5 7 6 2 4
操作:
1 3 2
4 4 7
3 5 1
则最终数列为：
7 9 9 10 5

对于这道题，如果我们朴素地对每个操作，都从l到r循环，给a[i]加上x的话，时间复杂度会是O(nm)>1e8，造成超时(time limit exceeded)。于是差分就出现了。

差分，就是在区间的开头和结尾分别打上标记的一种操作。比如在这道题中，我们称原数组为a，标记数组为b。对于每个操作，我们让b[l]+=x,b[r+1]-=x;这么做有什么用呢？我们观察b的前缀和数组。

前缀和数组sum[i]的值就等于经过m次操作，从1到i位的数之和增大了多少。那么如何求l~r的数之和增大了多少呢？显然为sum[r+1]-sum[l]。

于是，对于每个询问，我们只需要输出原数组在l、r+1的前缀和之差 加上 b数组在l、r+1的前缀和之差。

---

那么，如何将差分运用到sqy的锡纸烫这道题呢？
首先，要从题目给出的数据范围揣摩算法。我们看到一个有点反常的地方：(1≤xi≤1e6,0≤yi≤2^31−1)。为什么xi和yi的最大值差那么远呢？因为xi最大也不超过1e6，所以我们可以从这里入手。

首先，感性认识一下可以确定，sqy获得最多钱的那一天，一定是某位客人刚办卡而没开始消费的一天，也就是某个x[i]。那我们就可以从min x[i]到max x[i]循环。在这个循环中，有三个变量参与，它们分别是：cnt(i天有多少客人消费)、now(i天sqy手中的钱)、ans（我们要输出的值）。

for (i,？,？)
	{
		cnt+=c[i];
		now+=b[i]; now-=cnt;
		ans=max(ans,now);	
	}

既然cnt是i天有多少客人消费的前缀和，那么c显然就是某天有多少人消费的标记数组。b数组同理。具体的代码实现请继续思考。奥力给！

友情链接：
章鱼哥：https://fishercat.top/
姜总：https://jjhqwq.top/

打赏