好久没做反悔贪心了，写篇题解纪念一下。

第一问的答案显然是好求的，贪心地把更大的 $f_i$ 换到前面即可。不妨记第一问的答案为 $D$（其实题面也定义了这个）。

对于第二问，我们定义：

$$p_i=x+\sum^{i-1}_{j=1}f_j-\sum^i_{j=1}d_j$$

说人话就是，$p_i$ 表示到了点 $i$ 后的剩余油量。$p_i \ge 0$ 表示可以到 $i$，$p_i<0$ 表示到不了 $i$。

也就是说，我们要保证对于所有 $1 \le i \le D$，$p_i \ge 0$。

于是就有：

$$x+\sum^{i-1}_{j=1}f_j \ge \sum^i_{j=1}d_j$$

这个式子很麻烦，因为如果 $i>\frac{n}{2}$（因为 $n$ 是偶数所以没有下取整），那么有些交换是不会影响 $f_j$ 的前缀和的。

于是，我们对 $i>\frac{n}{2}$ 将式子变形如下：

$$x+\sum^{n-i}_{j=1}f_j+\sum^{i}_{j=n-i+1}f_j \ge \sum^i_{j=1}d_j$$

并且注意到，式子的第三项不会变化，所以可以将其当作常数。也就是说：

$$x+\sum^{n-i}_{j=1}f_j \ge \sum^i_{j=1}d_j-\sum^{i}_{j=n-i+1}f_j$$

发现 $n-i \le \frac{n}{2}$，于是我们就只限制了对于 $i \le \frac{n}{2}$ 的 $f_i$ 前缀和。并且交换一定就是会加上后面权值减去前面权值！

接下来就是好做的了。开一个堆，记录所有的 $1 \le j \le i$ 的 $f_{n-j+1}-f_j$，每次 $f_i$ 的前缀和不够大的时候就交换前面差距最大的就行了。

复杂度 $O(n \log n)$。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define f(i,j) ((i)*(k+1)+(j))
const int N=5e5+10,mod=998244353;
int d[N];
int f[N];
int sf[N];
int tf[N];
int k[N];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n,x;
	cin>>n>>x;
	for(int i=1;i<=n;i++) cin>>d[i],d[i]+=d[i-1];
	for(int i=1;i<=n;i++) cin>>f[i],tf[i]=f[i],sf[i]=sf[i-1]+f[i];
	for(int i=1;i<=n/2;i++) if(tf[n-i+1]>tf[i]) swap(tf[n-i+1],tf[i]);
	int p=0,s=x;
	for(int i=1;i<=n;i++)
	{
		if(d[i]>s)
		{
			p=i-1;
			break;
		}
		s+=tf[i];
	}
	if(p==0) p=n;
	cout<<p<<' ';
	for(int i=1;i<=n/2;i++) if(i+1<=p) k[i]=d[i+1];
	for(int i=1;i<n/2;i++) if(n-i+1<=p) k[i]=max(k[i],d[n-i+1]-sf[n-i]+sf[i]);
	priority_queue<int>pq;
	s=x;
	int c=0;
	for(int i=1;i<=n/2;i++)
	{
		s+=f[i];
		if(f[n-i+1]>f[i]) pq.push(f[n-i+1]-f[i]);
		while(s<k[i]) c++,s+=pq.top(),pq.pop();
	}
	cout<<c;
	return 0;
}

:::