C++ – Three Sequences 思维 差分

原题链接:

https://codeforces.com/contest/1406/problem/D

思路:

样例中a=2,-1,7,3;

差分为-3,8,-4;

设(b[1]=x)+(c[1]=y)=a[1];

∵b[1]<=b[2]<=b[3]...<=b[n] c[1]>=c[2]>=…>=c[n]

x+(y-3)=(x-1)+(y-2)=(x+1)+(y-4)=…=a[2]

∴b[2]=x c[2]=y-3为最优解

其他的解都会导致b[n]或者c[1]变大 使最后答案不是最小

即:差分>0时,将差分的值加入到b数组中;差分<0时,将差分加入到c数组中为最优解

第1个元素不加入sum!!!

设正差分的和为sum,则b[n]=x+sum y=c[1]=a[1]-x

ans=max(b[n],c[1])=max(x+sum,a[1]-x)

由函数y=x+sum与y=-x+a[1]的图像可得

当x=(a[1]-sum)/2时,ans取最小值 所以统计正差分的和sum和a[1]即可

对于修改操作,区间[l,r]中每个数都加x

所以内部差分不变,只需要更改l与r+1的差分

具体步骤:

1.若原差分l(或者r+1)>0,改变差分前需要从sum中减出来差分l(或者r+1)

sum改变前提:l!=1 r+1<=n

2.改变差分:差分[l]+=x; 差分[r+1]-=x;

3.若改变后差分l(或者r+1)>0,改变后sum+=差分l(或者r+1)

sum改变前提:l!=1 r+1<=n

4.若l==1,a[1]+=x; 5.与修改操作前同理,计算ans输出就行

#include
#include
#include
#define go(a,b,c) for(ll a=b;a<=c;a++)
using namespace std;
typedef long long ll;
ll n, a[100010], q, l, r, x, cha[100010], tot;
int main() {
	cin >> n;
	go(i, 1, n) {
		cin >> a[i];
		cha[i] = a[i] - a[i - 1];
		if (cha[i] > 0 && i != 1)
			tot += cha[i];
	}
	ll xx = (a[1] - tot) / 2;
	cout << max(xx + tot, a[1] - xx) << endl;
	cin >> q;
	while (q--) {
		cin >> l >> r >> x;
		if (l == 1)
			a[1] += x;
		else {
			tot -= cha[l] > 0 ? cha[l] : 0;
			cha[l] += x;
			tot += cha[l] > 0 ? cha[l] : 0;
		}
		if (r + 1 <= n) {
			tot -= cha[r + 1] > 0 ? cha[r + 1] : 0;
			cha[r + 1] -= x;
			tot += cha[r + 1] > 0 ? cha[r + 1] : 0;
		}
		xx = (a[1] - tot) / 2;
		cout << max(xx + tot, a[1] - xx) << endl;
	}
	return 0;
}

发表回复