专栏文章

P1315题解

AAwsdkl
P1315题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minftub4
此快照首次捕获于
2025/12/02 01:43
3 个月前
此快照最后确认于
2025/12/02 01:43
3 个月前
查看原文
不是你们都是怎么贪心的？我怎么一个都看不懂？
不难发现，答案为以下式子：
ans=∑i=2n(timi×cnti)+∑Ti。\begin{align*} ans &= \displaystyle\sum_{i=2}^{n} (tim_i \times cnt_i) + \displaystyle\sum T_i\text{。} \end{align*}
其中，timitim_i 表示车到第 ii 个站的时间，cnticnt_i 表示在第 ii 个站下车的人数。
我们再来推一波 timtim 的式子，设 beibe_i 为从 ii 出发的时间，则：
timi=bei−1+di−1。\begin{align*} tim_i &= be_{i-1} + d_{i-1}\text{。} \end{align*}
其中 dd 就是题目给出的 DD，为了好看我用的小写。
再推 bebe 的式子，设 laila_i 为第 ii 个站最后一个乘客到达的时间，则：
bei=max⁡(lai,bei−1+di−1)。\begin{align*} be_i = \max(la_i, be_{i-1}+d_{i-1})\text{。} \end{align*}
发现这是一个递推式，拆开得到：
bei=max⁡(lai,max⁡(lai−1+di−1,bei−2+di−2+di−1))，\begin{align*} be_i = \max(la_i, \max(la_{i-1}+d_{i-1}, be_{i-2}+d_{i-2}+d_{i-1}))\text{，} \end{align*}
通过瞪眼法不难得到最终的式子是：
bei=max⁡(lai,max⁡1≤j≤i−1(laj+∑j≤k≤i−1dk))。\begin{align*} be_i=\max(la_i, \displaystyle\max_{1 \le j \le i-1}( la_j + \displaystyle\sum_{j \le k \le i-1}d_k))\text{。} \end{align*}
把 dd 的求和写成前缀和的形式，令 prei=∑1≤j≤i−1djpre_i = \displaystyle\sum_{1 \le j \le i-1}d_j，则有：
bei=max⁡(lai,max⁡1≤j≤i−1(laj−prej)+prei)=max⁡(lai−prei,max⁡1≤j≤i−1(laj−prej))+prei=max⁡1≤j≤i(laj−prej)+prei。\begin{align*} be_i&=\max(la_i, \displaystyle\max_{1 \le j \le i-1}( la_j - pre_j)+ pre_i )\\ &=\max(la_i - pre_i, \displaystyle\max_{1 \le j \le i-1}( la_j - pre_j))+ pre_i\\ &=\displaystyle\max_{1 \le j \le i}(la_j - pre_j) + pre_i\text{。} \end{align*}
再将式子合并到答案的式子中：
ans=∑i=2n(timi×cnti)+∑Ti=∑i=2n((bei−1+di−1)×cnti)+∑Ti=∑i=2n((max⁡1≤j≤i−1(laj−prej)+prei−1+di−1)×cnti)+∑Ti=∑i=2n((max⁡1≤j≤i−1(laj−prej)+prei)×cnti)+∑Ti。\begin{align*} ans &= \displaystyle\sum_{i=2}^{n} (tim_i \times cnt_i) + \displaystyle\sum T_i\\ &= \displaystyle\sum_{i=2}^{n} \left( (be_{i-1}+d_{i-1})\times cnt_i\right) +\displaystyle\sum T_i\\ &= \displaystyle\sum_{i=2}^{n}\left(\left(\displaystyle\max_{1 \le j \le i-1}(la_j - pre_j) + pre_{i-1}+d_{i-1}\right)\times cnt_i\right)+\displaystyle\sum T_i \\ &= \displaystyle\sum_{i=2}^{n}\left(\left(\displaystyle\max_{1 \le j \le i-1}(la_j - pre_j) + pre_{i}\right)\times cnt_i\right)+\displaystyle\sum T_i\text{。} \end{align*}
然后他们就开始贪心了。但是我没看懂，所以我只能分析这个式子。
我们现在能修改的是从 ii 到 nn 的 prepre，ii 可以自选。修改为 prei→n←prei→n−1pre_{i \to n} \leftarrow pre_{i\to n}-1，然后再 di−1←di−1−1d_{i-1} \leftarrow d_{i-1}-1。修改只能在 di−1>0d_{i-1} > 0 时发生。
观察 ansans 的最终式子，我们假设 laj−prejla_j - pre_j 就是 max⁡\max 选的值，当前选择修改的是 kk，考虑对 ii 的贡献的影响。原贡献为 (laj−prej+prei)×cnti(la_j-pre_j+pre_i) \times cnt_i，现有以下三种情况：
  1. k≤jk \le j：此时贡献变为 (laj−(prej−1)+(prei−1))×cnti=(laj−prej+prei)×cnti(la_j-(pre_j-1)+(pre_i-1))\times cnt_i = (la_j - pre_j + pre_i) \times cnt_i，无变化；
  2. j<k≤ij < k \le i：此时贡献变为 (laj−prej+prei−1)×cnti(la_j-pre_j+pre_i-1)\times cnt_i，变小了；
  3. i<ki < k：显然无变化。
现在很清楚了，我们只需要选在 ii 前面的 la−prela-pre 最大的那个点以后，且在 ii 前面的数即可使 ii 的贡献变小。原理是：若 laj−prejla_j-pre_j 变，就会加上一个数，而 preipre_i 也会减小同一个数，这时不变；使 laj−prejla_j-pre_j 不变，而使 preipre_i 减小一个数，则贡献就可以减小。
这时再贪心的想，我们对 j+1j+1 这个点进行修改，则贡献会减小的点一定是最多的，会一直到下一个 la−prela-pre 比 laj−prejla_j-pre_j 大的这个点。这样就很清楚了，相当于一个点能影响后面连续一段 la−prela-pre 比它小的点，也可以影响第一个比它大的点。我们将一个点和它能影响的点框成一个区间，然后只需要维护 la−prela-pre 即可。用线段树维护。
一个线段被修改是不是优的，就取决于它除了左端点以外的点的 cntcnt 的和的大小。按照这个为关键字，将线段存到一个优先队列中即可确定操作顺序。
然后就是修改时的细节了。修改一个线段后，由于不会修改线段的左端点，线段中有一个点（不是右端点，因为右端点本来就比左端点大）可能比左端点大，那么我们就在那个点对线段分割。而当线段左端点的 dd 被剪到 00 时，这就不能再减了，我们将左端点向右移动以为。由于要记录左端点的大小，而此时左端点被移动了，因此需要记录一个线段原始的左端点在哪里。
具体实现看代码吧。
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 5e6+5;

inline ll max(ll a, ll b) { return a > b ? a : b; }

struct Node
{
	ll maxn; int maxpos; ll lazy;
	Node friend operator+(const Node &a, const Node &b)
	{
		Node res;
		res.maxpos = (a.maxn >= b.maxn ? a.maxpos : b.maxpos);
		res.maxn = max(a.maxn, b.maxn);
		res.lazy = 0;
		return res;
	}
};


struct Pas
{
	int tim, l, r;
} pas[MAXN];
int la[MAXN];
int pre[MAXN];
int d[MAXN];
int cnt[MAXN];
ll sum[MAXN];
int n, m, k;
ll T;

struct SegmentTree
{
	#define lp (p<<1)
	#define rp (p<<1|1)
	Node tree[MAXN<<2];
	void push_up(int p)
	{
		tree[p] = tree[lp] + tree[rp];
	}
	void push_down(int p)
	{
		if(!tree[p].lazy) return;
		tree[lp].lazy += tree[p].lazy;
		tree[rp].lazy += tree[p].lazy;
		tree[lp].maxn += tree[p].lazy;
		tree[rp].maxn += tree[p].lazy;
		tree[p].lazy = 0;
	}
	void build(int s, int t, int p)
	{
		if(s == t)
		{
			tree[p].maxn = la[s] - pre[s];
			tree[p].maxpos = s;
			return;
		}
		int mid = (s + t) >> 1;
		build(s, mid, lp);
		build(mid+1, t, rp);
		push_up(p);
	}
	void add(int l, int r, int s, int t, int p, int x)
	{
		if(l <= s && t <= r)
		{
			tree[p].maxn += x;
			tree[p].lazy += x;
			return;
		}
		int mid = (s + t) >> 1;
		push_down(p);
		if(l <= mid) add(l, r, s, mid, lp, x);
		if(r > mid) add(l, r, mid+1, t, rp, x);
		push_up(p);
	}
	Node query(int l, int r, int s, int t, int p)
	{
		if(l <= s && t <= r) return tree[p];
		int mid = (s + t) >> 1;
		push_down(p);
		if(r <= mid) return query(l, r, s, mid, lp);
		if(l > mid) return query(l, r, mid+1, t, rp);
		return query(l, r, s, mid, lp) + query(l, r, mid+1, t, rp);
	}
}tree;

struct seg
{
	int l, r;      // 左右端点
	ll sum, lmax;  // cnt 的和，原始左端点位置
	seg(int _l = 0, int _r = 0, ll _sum = 0, ll _vis = 0) : l(_l), r(_r), sum(_sum), lmax(_vis) {}
	bool operator<(const seg &_) const { return sum < _.sum; }
};
priority_queue<seg> q;

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i < n; i++) scanf("%d", &d[i]), pre[i+1] = pre[i] + d[i];
	for(int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &pas[i].tim, &pas[i].l, &pas[i].r);
		la[pas[i].l] = max(la[pas[i].l], pas[i].tim);
		cnt[pas[i].r]++;
		T += pas[i].tim;
	}
	tree.build(1, n, 1);
	for(int i = 1; i <= n+1; i++) sum[i] = sum[i-1] + cnt[i];
	for(int i = 2, lst = 1, lstv = la[1] - pre[1]; i <= n; i++)
	{
		if(la[i] - pre[i] >= lstv) 
		{
			q.emplace(seg(lst, i, sum[i] - sum[lst], lst));
			lst = i;
			lstv = la[i] - pre[i];
		}
		if(i == n && lst != n) q.emplace(seg(lst, i+1, sum[i] - sum[lst], lst));
	}
	for(; k && !q.empty(); )
	{
		seg cur = q.top(); q.pop();
		if(cur.l == cur.r-1) // 特判一下
		{
			if(k <= d[cur.l]) tree.add(cur.l+1, n, 1, n, 1, k), d[cur.l] -= k, k = 0;
			else k -= d[cur.l], tree.add(cur.l+1, n, 1, n, 1, d[cur.l]), d[cur.l] = 0;
			continue;
		}
		ll lmax = max(tree.query(cur.l, cur.l, 1, n, 1).maxn, tree.query(cur.lmax, cur.lmax, 1, n, 1).maxn);
		ll maxn = tree.query(cur.l+1, cur.r-1, 1, n, 1).maxn;

		if(k > min((ll)d[cur.l], lmax - maxn))
		{
			tree.add(cur.l+1, n, 1, n, 1, min((ll)d[cur.l], lmax - maxn));
			k -= min((ll)d[cur.l], lmax - maxn);
			if(d[cur.l] > lmax - maxn)
			{
				int pos = tree.query(cur.l+1, cur.r-1, 1, n, 1).maxpos;
				if(cur.l < pos) q.emplace(seg(cur.l, pos, sum[pos] - sum[cur.l], cur.lmax));
				if(pos < cur.r) q.emplace(seg{pos, cur.r, sum[cur.r] - sum[pos], pos});
			}
			else if(cur.l+1 < cur.r) q.emplace(seg(cur.l+1, cur.r, sum[cur.r] - sum[cur.l+1], cur.lmax));
			d[cur.l] -= min((ll)d[cur.l], lmax - maxn);
			continue;
		}
		tree.add(cur.l+1, n, 1, n, 1, k);
		d[cur.l] -= k;
		k = 0;
	}
	
	for(int i = 1; i < n; i++) pre[i+1] = pre[i] + d[i];
	ll ans = -T;
	for(int i = 2; i <= n; i++)
	{
		ans += cnt[i] * (tree.query(1, i-1, 1, n, 1).maxn + pre[i]);
	}
	printf("%lld\n", ans);

	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...