「2020-09-06联考」分块大师

题目链接

题意

$n$ 个均匀的物体，进行 $k(k\leq2)$ 次切割后再把 $n+k$ 个物品分为两组，最小化：

$\epsilon=\frac{\mid\sum_{i\in S}V_i-\sum_{i\in T}V_i\mid}{\sum_{i=1}^{n+k}V_i}+\frac{\mid\sum_{i\in S}m_i-\sum_{i\in T}m_i\mid}{\sum_{i=1}^{n+k}m_i}$

思路

由于可以切两次，猜想 $\epsilon=0$。

把每个物品看成一个矩形，长为 $V$，面积为 $m$（宽为 $\rho$），然后按高排序后顺次拼接在一起。

例如，样例

4
2 2 3 3
1 2 3 4

即为

现在要截取长为 $\frac12\sum_{i=1}^nV_i$，面积为 $\frac12\sum_{i=1}^nm_i$ 的图形，我们把一条长为 $\frac12\sum_{i=1}^nV_i$ 的线段从左到右移动，则它覆盖的面积一定单调不降，并一定会在某个位置达到 $\frac12\sum_{i=1}^nm_i$。

因此构造完矩形后，可以二分出使面积恰好一半的线段所在的位置，将它端点所在位置的矩形切开即可。线段有两个端点，所以最多需要切两个矩形。

实现

预处理前缀和，即可 $O(\log n)$ 求线段覆盖矩形面积（使用分段函数，二分出线段端点在哪个矩形上）。

特别注意起始与结束端点在同一矩形上的情况。

时间复杂度 $O(T\log^2n)$，精度要求较高，硬是用了调整 $eps$ 和 long double 才过。

代码

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int N=1e5;
const long double eps=5e-9;
int t,n;
struct item {
    int id;
    int v,m;
};
item a[N+1];
long long sumv[N+1],summ[N+1];
int read()
{
    int ret=0;
    char c=getchar();
    while(!isdigit(c)) {
        c=getchar();
    }
    while(isdigit(c)) {
        ret=ret*10+c-'0';
        c=getchar();
    }
    return ret;
}
long double f(long double v)
{
    int pos=upper_bound(sumv+1,sumv+n+1,v)-sumv-1;
    return summ[pos]+1.0*a[pos+1].m*(v-sumv[pos])/a[pos+1].v;
}
int main()
{
    freopen("grandmaster.in","r",stdin);
    freopen("grandmaster.out","w",stdout);
    t=read();
    while(t--) {
        n=read();
        for(int i=1;i<=n;++i) {
            a[i].id=i;
        }
        for(int i=1;i<=n;++i) {
            a[i].v=read();
        }
        for(int i=1;i<=n;++i) {
            a[i].m=read();
        }
        sort(a+1,a+n+1,[](const item x,const item y) {
            return 1ll*x.m*y.v<1ll*y.m*x.v;
        });
        for(int i=1;i<=n;++i) {
            sumv[i]=sumv[i-1]+a[i].v;
            summ[i]=summ[i-1]+a[i].m;
        }
        long double fro,to;
        for(long double l=0,r=1.0*sumv[n]/2;;) {
            long double mid=(l+r)/2,tem=f(mid+1.0*sumv[n]/2)-f(mid);
            if(abs(tem-1.0*summ[n]/2)<eps) {
                fro=mid,to=mid+1.0*sumv[n]/2;
                break;
            }
            if(2*tem<summ[n]) {
                l=mid;
            } else {
                r=mid;
            }
        }
        int posfro=lower_bound(sumv+1,sumv+n+1,fro)-sumv,posto=lower_bound(sumv+1,sumv+n+1,to)-sumv;
        puts("2");
        printf("%d %.15Lf\n",a[posfro].id,(fro-sumv[posfro-1])/a[posfro].v);
        printf("%d %.15Lf\n",posfro==posto?n+1:a[posto].id,posfro==posto?((to-sumv[posto-1])/a[posto].v-(fro-sumv[posfro-1])/a[posfro].v)/(1-(fro-sumv[posfro-1])/a[posfro].v):(to-sumv[posto-1])/a[posto].v);
        static bool inS[N+3];
        for(int i=1;i<=posfro;++i) {
            inS[a[i].id]=true;
        }
        for(int i=posfro+1;i<=posto;++i) {
            inS[a[i].id]=false;
        }
        for(int i=posto+1;i<=n;++i) {
            inS[a[i].id]=true;
        }
        inS[n+1]=false,inS[n+2]=true;
        for(int i=1;i<=n+2;++i) {
            putchar(inS[i]?'0':'1'),putchar(' ');
        }
        putchar('\n');
    }
    return 0;
}