P9579「Cfz Round 1」Elevator

思路

假设 \(a_i\) 和 \(b_i\) 的最大值是 \(maxn\)。

可以发现序列 \(1,2,3 \cdots maxn\) 一定是要构造的序列的子序列。

那么，这种情况下，一定满足了所有的 \(a_i<b_i\)，因为 \(a_i\neq b_i\)，所以我们只需要单独满足所有的 \(a_i>b_i\) 就可以了。

对于所有的 \(a_i>b_i\)，我们有两种选择，到了 \(a_i\) 后，序列往回减倒 \(b_i\) 再加回来，或者序列最后达到 \(maxn\) 再往回减倒 \(b_i\)。

第一种情况会使答案增加 \(2\times (a_i-b_i)\)，第二种情况会使答案增加 \(maxn-b_i\)。

那么，我们可以先对 \(b_i\) 排序，然后枚举 \(i\)，\(i\) 以前的用前一种，\(i\) 以后的用后一种。

39pts WA code

#include<bits/stdc++.h>
using namespace std;
struct node{long long a,b;}spe[500005];
inline bool cmp(node a,node b){return a.b<b.b;}
long long n,a1,b1,cnt,maxn,ans,sum;
int main()
{
	scanf("%lld",&n);
	for(long long i=1;i<=n;++i)
	{
		scanf("%lld%lld",&a1,&b1);
		if(a1>b1) spe[++cnt].a=a1,spe[cnt].b=b1;//记录ai>bi的情况
		maxn=max(maxn,max(a1,b1));
	}
	ans=0x3f3f3f3f3f3f3f3f;
	sort(spe+1,spe+cnt+1,cmp);//排序
	for(long long i=1;i<=cnt;++i)
	{
		ans=min(ans,sum+maxn-spe[i].b);//取最小
		sum+=2*(spe[i].a-spe[i].b);//记录前i所增加的答案
	}
	printf("%lld",min(sum,ans)+maxn);//最后的sum是全部都选择第一种的答案
	return 0;
}

WA 了，这是为什么呢？仔细想了一下，如果有两组 \(a_i\) 和 \(b_i\) 有重叠部分，如 \(1,5\) 和 \(3,7\) 那么如果这两组都选择第一种方式，那么增加的答案应该是 \(2\times(7-1)\) 而非 \(2\times(5-1)+2\times(7-3)\)。

所以我们再记录前面所有的 \(a_i\) 的最大值为 \(lasa\)，那么在处理第 \(i+1\) 组时，如果 \(b_i<lasa\) 的话，增加的答案就是 \(2\times(a_i-lasa)\)，否则的话就还是原来的答案贡献，合在一起就是 \(2\times(a_i-\max(lasa,b_i))\)。

AC code

#include<bits/stdc++.h>
using namespace std;
struct node{long long a,b;}spe[500005];
inline bool cmp(node a,node b){return (a.b!=b.b)?a.b<b.b:a.a<b.a;}
long long n,a1,b1,cnt,maxn,ans,sum,lasa;
int main()
{
	scanf("%lld",&n);
	for(long long i=1;i<=n;++i)
	{
		scanf("%lld%lld",&a1,&b1);
		if(a1>b1) spe[++cnt].a=a1,spe[cnt].b=b1;
		maxn=max(maxn,max(a1,b1));
	}
	ans=0x3f3f3f3f3f3f3f3f;
	sort(spe+1,spe+cnt+1,cmp);
	for(long long i=1;i<=cnt;++i)
	{
		ans=min(ans,sum+maxn-spe[i].b);
		sum+=2*(max(0ll,spe[i].a-max(lasa,spe[i].b))),lasa=max(lasa,spe[i].a);
	}
	printf("%lld",min(sum,ans)+maxn);
	return 0;
}