526互联

Atcoder Grand Contest 062 D - Walk Around Neighborhood

发布时间 2023-05-26 23:23:30作者: tzc_wk

csy/bx wjz/bx

首先将 \(a\) 排序，如果 \(\sum\limits_{i=1}^{n-1}a_i<a_n\) 显然就是 \(-1\)，否则必然有解。

先发现一个 trivial 的事情，就是答案一定位于 \([\dfrac{a_n}{2},a_n]\) 中，这是因为我们判掉无解的条件之后，我们必然可以用前面的步数走到以 \((a_n,0),(0,a_n),(-a_n,0),(0,-a_n)\) 为顶点的正方形上然后在边界上来回徘徊用掉剩下的步数，最后用掉 \(a_n\) 回到原点。而如果边长小于 \(\dfrac{a_n}{2}\)，那那个 \(a_n\) 一用就横跨整个正方形了，肯定没法完成任务。

现在考虑枚举这个半径 \(d\)，考虑 meet-in-the-middle，等价于我们要将所有步数分成两个集合 \(S,T\)，使得它们都能走到以 \((d,0),(0,d),(-d,0),(0,-d)\) 为顶点的正方形上——显然只要能走上去，由于 \(\dfrac{a_n}{2}\le d\le a_n\)，剩下的步数肯定都可以在边界上来回徘徊，而且根据对称性，两部分肯定可以汇合。因此我们现在只要 check 什么样的集合能够走到边界上即可，考虑 \(\le d\) 的那些元素，如果它们的和超过 \(d\) 那显然可以，否则，如果存在一个 \(>d\) 的元素 \(x\)，满足 \(\le d\) 的元素之和 \(\ge x-d\)，那我们肯定可以先走到 \((x-d,0)\) 然后一步走到 \((-d,0)\)，否则可以证明是不行的。

从全局的角度考虑，因为 \(d\) 是超过最大元素的一半的，所以如果存在元素 \(>d\) 那肯定限制更松，显然是更有利的，并且这个元素肯定是越小越好，因此考虑找到 \(>d\) 的最小和次小元素 \(x,y\)，显然 \(x\) 必然存在，因为 \(a_n\ge d\)，但 \(y\) 有可能不存在，因此分情况讨论：

  • 如果 \(y\) 不存在，那么相当于我们要将 \(\le d\) 的元素分成两部分，大小分别 \(\ge x-d,\ge d\)，直接 bitset 优化背包找到可能组合出来的和然后在里面 _Find_next 即可。
  • 如果 \(y\) 存在，那么要求分成的两部分大小分别 \(\ge x-d,\ge y-d\)，同理 bitset 做。

时间复杂度 \(\dfrac{n^2}{\omega}\)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=2e5;
int n,a[MAXN+5];bitset<MAXN+5>f;
int main(){
	scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1);ll sum=0;for(int i=1;i<n;i++)sum+=a[i];
	if(sum<a[n])return puts("-1"),0;
	f[0]=1;
	for(int i=a[n]/2,j=0,s=0;i<=a[n];i++){
		while(j<n&&a[j+1]<i)f|=(f<<a[++j]),s+=a[j];
		int x=a[j+1]-i,y=(j==n-1)?i:(a[j+2]-i),pos=f._Find_next(x-1);
		if(s-pos>=y)return printf("%d\n",i),0;
	}
	return 0;
}