agc062d

tzc_wk · 2023-05-26 23:16:38 · 题解

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;
}